fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. int p[501][501], dp[501][501], zero[501][501]; 
  4. //zero[i][j] will store whether any value is <=0 in the path from (0,0) to (i,j) 
  5. int max(int a, int b)
  6. {
  7.   return (a > b ? a : b);   
  8. }
  9. int main()
  10. {
  11.     int times;
  12.     scanf("%d", &times);
  13.  
  14.     while (times--)
  15.     {
  16.           int r, c, i, j;
  17.           scanf("%d %d", &r, &c);
  18.           for (i = 0; i < r; i++)
  19.           {
  20.               for (j = 0; j < c; j++)
  21.               {
  22.                   scanf("%d", &p[i][j]);
  23.               }
  24.           }
  25.           int mid,lo=1,hi=(r+c)*1000+6,min=1048577;
  26.           while(lo<=hi)
  27.           {
  28.           	  mid=(lo+hi)>>1;
  29.           	  for (i = 0; i < r; i++)
  30. 		      {
  31. 		          for (j = 0; j < c; j++)
  32. 		          {
  33. 		          	dp[i][j]=p[i][j];
  34. 		          	zero[i][j]=0;	
  35. 		          }
  36. 		      }
  37. 		      dp[0][0]=mid;
  38. 	          // top row
  39. 	          for (j = 1; j < c ; j++)
  40.               {
  41.               	  dp[0][j] += dp[0][j-1]; 
  42. 				  if(dp[0][j]<=0 || zero[0][j-1]==1)
  43. 				  {
  44. 				  	zero[0][j]=1;
  45. 				  }	
  46.               }
  47. 	          // first column
  48. 	          for (i = 1; i < r ; i++)
  49.               {
  50.               	  dp[i][0] += dp[i-1][0];	
  51.               	  if(dp[i][0]<=0 || zero[i-1][0]==1)
  52. 				  {
  53. 				  	zero[i][0]=1;
  54. 				  }	
  55.               }
  56.  
  57. 	          // non boundary elements
  58. 	          for (i = 1; i < r ; i++)
  59. 	          {
  60. 	              for (j = 1; j < c ; j++)
  61. 	              {
  62. 	              	  if(dp[i-1][j] == dp[i][j-1])
  63. 	              	  {
  64. 	              	  		dp[i][j] += dp[i-1][j];
  65. 	                  		zero[i][j] = std::min(zero[i-1][j],zero[i][j-1]);	
  66. 	              	  }
  67. 	              	  else if(zero[i-1][j] > zero[i][j-1] || ((zero[i-1][j] == zero[i][j-1]) && (dp[i-1][j] < dp[i][j-1])))
  68. 	              	  {
  69. 	              	  		dp[i][j] += dp[i][j-1];
  70. 	              	  		zero[i][j] = zero[i][j-1];
  71. 	              	  }else
  72. 	              	  {
  73. 	              	  		dp[i][j] += dp[i-1][j];
  74. 	                  		zero[i][j] = zero[i-1][j];
  75. 					  }
  76. 	              	  if(dp[i][j]<=0)zero[i][j]=1;
  77. 	              }
  78. 	          }
  79.  
  80. 	         if(zero[r-1][c-1]==0 && min > mid) min=mid;
  81. 	         if(zero[r-1][c-1]==0)hi=mid-1;
  82. 	         else lo=mid+1;
  83.           }
  84.       	  printf("%d\n", min);
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0s 6240KB
comments (?)
stdin
copy 
1
4 4
0  1 -9 -9
0 -9 -9 -9
0 -9 -9 -9
0  0  0  0
stdout
copy 
1
https://ideone.com/hXBw6c
language:
C++ (gcc 8.3)
created:
10 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!