fork download
copy 
  1. /* Author haleyk10198 */
  2. /* CF handle: haleyk100198*/
  3. /* FOR ACM-ICPC WF*/
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7. using ll = long long;
  8. using vi = vector<int>;
  9. using vvi = vector<vi>;
  10. using pii = pair<int, int>;
  11.  
  12. #define pb push_back
  13.  
  14. constexpr auto MOD = 1000000007LL;
  15. constexpr auto LINF = (1LL<<60);
  16. constexpr auto INF = 2147483647LL;
  17. constexpr auto PI = 3.1415926535897932384626433;
  18. constexpr auto EPS = 1E-9;
  19.  
  20. template<typename T1, typename T2>
  21. ostream& operator<<(ostream& out, const pair<T1, T2> p){
  22. 	out << p.first << ' ' << p.second;
  23. 	return out;
  24. }
  25.  
  26. template <typename T1, typename T2>
  27. istream& operator>>(istream& in, pair<T1, T2> &p){
  28. 	in >> p.first >> p.second;
  29. 	return in;
  30. }
  31.  
  32. auto printVector = []<typename T>(ostream& out, vector<T> v){
  33. 	copy(v.begin(), v.end(), ostream_iterator<T>(out, " "));
  34. };
  35.  
  36. /*
  37.  * This is a simplex solver. Given m x n matrix A, m-vector b, n-vector c,
  38.  * finds n-vector x such that
  39.  *
  40.  *  A x <= b (component-wise)
  41.  *
  42.  * maximizing
  43.  *
  44.  *  < x , c >
  45.  *
  46.  * where <x,y> is the dot product of x and y.
  47.  *
  48.  */
  49. typedef long double DOUBLE;
  50. typedef vector<DOUBLE> VD;
  51. typedef vector<VD> VVD;
  52. typedef vector<int> VI;
  53.  
  54. struct LPSolver {
  55.   int m, n;
  56.   VI B, N;
  57.   VVD D;
  58.  
  59.   LPSolver(const VVD &A, const VD &b, const VD &c) : 
  60.     m(b.size()), n(c.size()), N(n+1), B(m), D(m+2, VD(n+2)) {
  61.     for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
  62.     for (int i = 0; i < m; i++) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i]; }
  63.     for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
  64.     N[n] = -1; D[m+1][n] = 1;
  65.   }
  66.  
  67.   void Pivot(int r, int s) {
  68.     for (int i = 0; i < m+2; i++) if (i != r)
  69.       for (int j = 0; j < n+2; j++) if (j != s)
  70. 	D[i][j] -= D[r][j] * D[i][s] / D[r][s];
  71.     for (int j = 0; j < n+2; j++) if (j != s) D[r][j] /= D[r][s];
  72.     for (int i = 0; i < m+2; i++) if (i != r) D[i][s] /= -D[r][s];
  73.     D[r][s] = 1.0 / D[r][s];
  74.     swap(B[r], N[s]);
  75.   }
  76.  
  77.   bool Simplex(int phase) {
  78.     int x = phase == 1 ? m+1 : m;
  79.     while (true) {
  80.       int s = -1;
  81.       for (int j = 0; j <= n; j++) {
  82. 	if (phase == 2 && N[j] == -1) continue;
  83. 	if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
  84.       }
  85.       if (D[x][s] >= -EPS) return true;
  86.       int r = -1;
  87.       for (int i = 0; i < m; i++) {
  88. 	if (D[i][s] <= 0) continue;
  89. 	if (r == -1 || D[i][n+1] / D[i][s] < D[r][n+1] / D[r][s] ||
  90. 	    D[i][n+1] / D[i][s] == D[r][n+1] / D[r][s] && B[i] < B[r]) r = i;
  91.       }
  92.       if (r == -1) return false;
  93.       Pivot(r, s);
  94.     }
  95.   }
  96.  
  97.   DOUBLE Solve(VD &x) {
  98.     int r = 0;
  99.     for (int i = 1; i < m; i++) if (D[i][n+1] < D[r][n+1]) r = i;
  100.     if (D[r][n+1] <= -EPS) {
  101.       Pivot(r, n);
  102.       if (!Simplex(1) || D[m+1][n+1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
  103.       for (int i = 0; i < m; i++) if (B[i] == -1) {
  104. 	int s = -1;
  105. 	for (int j = 0; j <= n; j++) 
  106. 	  if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
  107. 	Pivot(i, s);
  108.       }
  109.     }
  110.     if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
  111.     x = VD(n);
  112.     for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n+1];
  113.     return D[m][n+1];
  114.   }
  115. };
  116.  
  117. inline int sum(int x){
  118. 	return x*(x+1)/2;
  119. }
  120.  
  121. int main(){
  122. 	#ifdef LOCAL
  123. 		freopen("input.txt","r",stdin);
  124. //		freopen("output.txt","w",stdout);
  125. 	#endif
  126. 	ios_base::sync_with_stdio(false);
  127.  
  128. 	int T; cin >> T;
  129. 	for(int no = 1; no <= T; no++){
  130. 		int n, m; cin >> n >> m;
  131. 		VVD A = VVD(2);
  132. 		VD B = VD(2);
  133. 		VD C;
  134.  
  135. 		int sz = 0;
  136.  
  137. 		B[0] = n, B[1] = m;
  138. 		for(int i = 0; i <= n; i++)
  139. 			for(int j = not i; j <= m; j++){
  140. 				if(sum(i)*(j+1) > n || sum(j)*(i+1) > m)
  141. 					break;
  142. 				A[0].pb(i);
  143. 				A[1].pb(j);
  144. 				sz++;
  145. 				C.pb(1);
  146. 			}
  147.  
  148. 		for(int i = 0; i < sz; i++){
  149. 			A.pb(VD(sz));
  150. 			A.back()[i] = 1;
  151. 			B.pb(1);
  152. 		}
  153.  
  154. 		LPSolver solver(A, B, C);
  155. 		VD x;
  156. 		DOUBLE value = solver.Solve(x);
  157.  
  158. 		cout << "Case #" << no << ": ";
  159.  
  160. 		cout << (int) (value+EPS) << endl;
  161. 	}
  162.  
  163. 	return 0;
  164. }
  165.  
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
2
2 0
4 5
stdout
copy 
Case #1: 1
Case #2: 5
https://ideone.com/VA2Uvw
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!