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