fork(1) download
copy 
  1. #include <cstring>
  2. #include <iostream>
  3. using namespace std;
  4. #define SIZE 51
  5. #define ULL long long
  6.  
  7. int minIndex(int size, ULL arr[])
  8. {
  9.     int i=0,index = 0;
  10. 	ULL min=arr[0];
  11. 	for(i=1;i<size;++i)
  12. 	{
  13. 		if(arr[i] < min)
  14. 		{
  15. 			min = arr[i];
  16. 			index = i;
  17. 		}
  18. 	}
  19. 	return index;
  20. }
  21.  
  22. int maxIndex(int size, ULL arr[])
  23. {
  24. 	int i=0,index = 0;
  25. 	ULL min=arr[0];
  26. 	for(i=1;i<size;++i)
  27. 	{
  28. 		if(arr[i] > min)
  29. 		{
  30. 			min = arr[i];
  31. 			index = i;
  32. 		}
  33. 	}
  34. 	return index;
  35. }
  36.  
  37. ULL final;
  38. void backtrack(ULL mat[SIZE][SIZE], 
  39. 	ULL sumR[SIZE][SIZE], ULL sumC[SIZE][SIZE],
  40. 	int sr, int sc, int er, int ec, ULL alice, ULL bob) 
  41. 	{
  42. 		ULL check[4];
  43. 		ULL all;
  44.  
  45. 		if(sr < 1 || sc < 1 || (sr > er) || (sc > ec))
  46. 		{
  47. 			if(alice == bob)
  48. 			{
  49. 				all = alice+bob;
  50. 				if(all > final)
  51. 					final = all;
  52. 			}
  53. 			else
  54. 			{
  55. 				if(bob > final)
  56. 					final = bob;
  57. 			}
  58. 			return ;
  59. 		}
  60. 		// for bob we know the pririty.
  61. 		check[0] = sumR[sr][ec] - sumR[sr][sc-1]; 
  62.     	check[1] = sumR[er][ec] - sumR[er][sc-1];
  63.     	check[2] = sumC[er][sc] - sumC[sr-1][sc];
  64.     	check[3] = sumC[er][ec] - sumC[sr-1][ec];
  65.      	int ret = minIndex(4,check);
  66.  
  67.      	switch(ret)
  68. 	    {
  69. 			case 0: ++sr; break;
  70. 		    case 1:--er;break;
  71. 		    case 2:++sc;break;
  72. 		    case 3:--ec;
  73. 		}
  74.  
  75. 		alice += check[ret];
  76.  
  77.  
  78. 		//if((sr > er) || (sc > ec))
  79. 		{
  80. 			if(alice == bob)
  81. 			{
  82. 				all = alice+bob;
  83. 				if(all > final)
  84. 					final = all;
  85. 			}
  86. 			else
  87. 			{
  88. 				if(bob > final)
  89. 					final = bob;
  90. 			}
  91. 		}
  92.  
  93. 		// it was done for bob 
  94. 		check[0] = sumR[sr][ec] - sumR[sr][sc-1]; 
  95.     	check[1] = sumR[er][ec] - sumR[er][sc-1];
  96.     	check[2] = sumC[er][sc] - sumC[sr-1][sc];
  97.     	check[3] = sumC[er][ec] - sumC[sr-1][ec];
  98.  
  99.      	ret = maxIndex(4,check);
  100.      	ULL max = check[ret];
  101.      	int in=0;
  102.      	for(in=ret;in<4;++in)
  103.      	{
  104. 			if(max == check[in])
  105. 			{
  106. 				// got minimum for this backtrack for next
  107. 				// after changing the parameters sr, er, sc, ec
  108. 				switch(in)
  109. 			    {
  110. 					case 0: ++sr;break;
  111. 				    case 1:--er;break;
  112. 				    case 2:++sc;break;
  113. 				    case 3:--ec;
  114. 				}
  115. 				//bob += check[ret];
  116. 				backtrack(mat, sumR, sumC, sr, sc, er, ec, alice, bob+max);
  117. 				//bob -= check[ret];
  118. 				switch(in)
  119. 			    {
  120. 					case 0: --sr;break;
  121. 				    case 1:++er;break;
  122. 				    case 2:--sc;break;
  123. 				    case 3:++ec;
  124. 				}
  125. 			}
  126. 		}
  127.  
  128. 		//if((sr > er) || (sc > ec))
  129. 		{
  130. 			if(alice == bob)
  131. 			{
  132. 				all = alice+bob;
  133. 				if(all > final)
  134. 					final = all;
  135. 			}
  136. 			else
  137. 			{
  138. 				if(bob > final)
  139. 					final = bob;
  140. 			}
  141. 		}		
  142. 	}
  143.  
  144. int main()
  145. {
  146.     int t,n,m,i,j,sr,er,sc,ec,ret,taken;
  147.  
  148.     ULL mat[SIZE][SIZE], row[SIZE], col[SIZE], sumR[SIZE][SIZE], sumC[SIZE][SIZE];
  149.  
  150.     ULL win,bob,alice,firstr,lastr,firstc,lastc;
  151.  
  152.     scanf("%d",&t);
  153.  
  154.  
  155.     while(t--)
  156.  
  157.     {
  158.  
  159. 	    scanf("%d %d",&n,&m);
  160.  
  161. 	    //memset(row,0,sizeof(ULL)*SIZE);
  162.  
  163. 	    //memset(col,0,sizeof(ULL)*SIZE);
  164.  
  165. 	    win = bob = alice = firstr = lastr = firstc = lastc = 0;
  166. 	    sr = er = sc = ec = ret = taken = 0;
  167. 	    for(i=0;i<=n;++i)
  168. 	    {
  169. 	    // TODO: required only 1 time
  170. 	     memset(sumR[i],0,sizeof(ULL)*SIZE);
  171. 	    }
  172.  
  173. 	    for(i=0;i<=m;++i)	
  174. 	    {
  175. 	     memset(sumC[i],0,sizeof(ULL)*SIZE);
  176. 	    }
  177. 	    for(i=1;i<=n;++i)
  178. 	    {
  179. 		    for(j=1;j<=m;++j)
  180. 		    {
  181. 			    scanf("%lld", &mat[i][j]);
  182. 			    sumR[i][j] += sumR[i][j-1] + mat[i][j];     
  183. 			    sumC[i][j] += sumC[i-1][j] + mat[i][j];
  184. 		    }
  185. 	    }
  186.  
  187. 	    final = 0;
  188. 	    backtrack(mat, sumR, sumC, 1, 1, n, m, 0, 0);
  189. 	    printf("%lld\n", final);
  190. 	}
  191. }
Success #stdin #stdout 0.02s 2688KB
comments (?)
stdin
copy 
1
4 4
83 43 69 43
35 45 39 33
 9 76 39 55
22 88 58 60
stdout
copy 
497
https://ideone.com/VxCqXe
language:
C++ (gcc 8.3)
created:
11 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!