fork(5) download 
  1. #include <cstdio>
  2. #include <cassert>
  3.  
  4. #define REP(i,a) for (int i = 0; i < (a); ++i)
  5. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  6. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  7.  
  8. #define MAX 50
  9.  
  10. //#define DEBUG 1
  11.  
  12. int T, R, C, tab;
  13.  
  14. typedef unsigned long long ull;
  15.  
  16. ull A[MAX+1][MAX+1], sum[MAX+2][MAX+2], asum;
  17.  
  18. ull alice( int rf, int rt, int cf, int ct );
  19. ull bob( int rf, int rt, int cf, int ct );
  20.  
  21. ull rectsum( int rf, int cf, int rt, int ct ) {
  22.     ull res = sum[rt+1][ct+1] - sum[rf][ct+1] - sum[rt+1][cf] + sum[rf][cf];
  23. 	//if (DEBUG) printf( "DEBUG rectsum( rf=%d, rt=%d, cf=%d, ct=%d ) = %llu\n", rf, rt, cf, ct, res );
  24. 	return res;
  25. }
  26.  
  27. void spaces( int n ) {
  28. 	REP(i, n) printf( " " );
  29. }
  30.  
  31. ull alice( int rf, int rt, int cf, int ct ) {
  32. 	tab += 2;
  33. 	//if (DEBUG) { spaces(tab); printf( "alice( act=%llu, rf=%d, rt=%d, cf=%d, ct=%d ) {\n", act, rf, rt, cf, ct ); }
  34. 	if ( rt < rf || ct < cf ) {
  35. 		//if ( act << 1 == asum ) half = act; // we found half
  36. 		//if ( act > max ) max = act;
  37. 		//if (DEBUG) { spaces(tab); printf( "}\n"); }
  38. 		//if (DEBUG) tab -= 2;
  39. 		return 0;
  40. 	}
  41. 	// first row
  42. 	ull min = rectsum(rf, cf, rf, ct);
  43. 	int flag = 0;
  44. 	// last row
  45. 	ull v2 = rectsum(rt, cf, rt, ct);
  46. 	if ( v2 < min ) { min = v2; flag = 1; }
  47. 	// first column
  48. 	ull v3 = rectsum(rf, cf, rt, cf);
  49. 	if ( v3 < min ) { min = v3; flag = 2; }
  50. 	// last column
  51. 	ull v4 = rectsum(rf, ct, rt, ct);
  52. 	if ( v4 < min ) { min = v3; flag = 3; }
  53.  
  54. 	//if (DEBUG) printf( "DEBUG: alice - flag=%d\n", flag );
  55.  
  56. 	ull res;
  57. 	switch ( flag ) {
  58. 		case 0: res = bob( rf+1, rt, cf, ct ); break;
  59. 		case 1: res = bob( rf, rt-1, cf, ct ); break;
  60. 		case 2: res = bob( rf, rt, cf+1, ct ); break;
  61. 		case 3: res = bob( rf, rt, cf, ct-1 ); break;
  62. 	}
  63. 	//if (DEBUG) { spaces(tab); printf( "} (alice)\n"); }
  64. 	tab -= 2;
  65. 	return res;
  66. }
  67.  
  68. ull bcache[MAX][MAX][MAX][MAX];
  69.  
  70. ull bob( int rf, int rt, int cf, int ct ) {
  71. 	tab += 2;
  72. 	//if (DEBUG) { spaces(tab); printf( "bob( act=%llu, rf=%d, rt=%d, cf=%d, ct=%d ) {\n", act, rf, rt, cf, ct ); }
  73. 	if ( rt < rf || ct < cf ) {
  74. 		//if ( act << 1 == asum ) half = act; // we found half
  75. 		//if ( act > max ) max = act;
  76. 		//if (DEBUG) { spaces(tab); printf( "} bob\n"); }
  77. 		tab -= 2;
  78. 		return 0;
  79. 	}
  80. 	if ( bcache[rf][rt][cf][ct] != -1 ) { return bcache[rf][rt][cf][ct]; }
  81. 	ull tmp, max;
  82. 	max = rectsum(rf, cf, rf, ct);
  83. 	//if (DEBUG) printf( "DEBUG: tmp=%llu\n", tmp );
  84. 	max += alice( rf+1, rt, cf, ct );
  85.  
  86. 	tmp = rectsum(rt, cf, rt, ct);
  87. 	//if (DEBUG) printf( "DEBUG: tmp=%llu\n", tmp );
  88. 	tmp += alice( rf, rt-1, cf, ct );
  89. 	if ( tmp > max ) max = tmp;
  90.  
  91. 	tmp = rectsum(rf, cf, rt, cf);
  92. 	//if (DEBUG) printf( "DEBUG: tmp=%llu\n", tmp );
  93. 	tmp += alice( rf, rt, cf+1, ct );
  94. 	if ( tmp > max ) max = tmp;
  95.  
  96. 	tmp = rectsum(rf, ct, rt, ct);
  97. 	//if (DEBUG) printf( "DEBUG: tmp=%llu\n", tmp );
  98. 	tmp += alice( rf, rt, cf, ct-1 );
  99. 	if ( tmp > max ) max = tmp;
  100. 	//if (DEBUG) { spaces(tab); printf( "} bob\n"); }
  101. 	//if (DEBUG) tab -= 2;
  102.  
  103. 	bcache[rf][rt][cf][ct] = max;
  104. 	return max;
  105. }
  106.  
  107. int main() {
  108. 	tab = 0;
  109. 	assert( scanf( "%d", &T ) == 1 );
  110. 	while ( T-- ) { // for each test case
  111. 		// init
  112. 		assert( scanf( "%d%d", &R, &C ) == 2 );
  113. 		asum = 0;
  114. 		REP( ci, C+1) sum[0][ci] = 0;
  115. 		//if (DEBUG) { REP (ci, C+1) printf( "%llu ", sum[0][ci]); printf( "\n"); }
  116. 		REP( ri, R) sum[ri][0] = 0;
  117. 		REP( ri, R ) {
  118. 			//if (DEBUG) printf( "%llu ", sum[ri][0] );
  119. 			REP( ci, C ) {
  120. 				assert( scanf( "%llu", &A[ri][ci] ) == 1 );
  121. 				asum += A[ri][ci];
  122. 				sum[ri+1][ci+1] = A[ri][ci] + sum[ri][ci+1] + sum[ri+1][ci] - sum[ri][ci];
  123. 				//if (DEBUG) printf( "%llu ", sum[ri+1][ci+1] );
  124. 			}
  125. 			//if (DEBUG) printf("\n");
  126. 		}
  127. 		REP(i1, R) REP(i2, R) REP(i3, C) REP(i4, C) bcache[i1][i2][i3][i4] = -1;
  128.  
  129. 		// Alice moves first
  130. 		ull bmax = alice( 0, R-1, 0, C-1 );
  131. 		//if (DEBUG) printf( "DEBUG: max=%llu, half=%llu\n", max, half );
  132. 		ull alice = asum - bmax;
  133. 		if ( alice == bmax ) printf( "%llu\n", asum );
  134. 		else if ( bmax > alice ) printf( "%llu\n", bmax );
  135. 		else printf( "%llu\n", alice );
  136. 	}
  137. 	return 0;
  138. }
Success #stdin #stdout 0.01s 51560KB
comments (?)
stdin 
1
4 3
4 1 4
1 6 1
1 1 1
3 2 3
stdout 
17
https://ideone.com/ENargR
language:
C++ (gcc 8.3)
created:
12 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!