fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. inline void fastRead_int(int &x) {
  3.  
  4. 	    register int c = getchar_unlocked();
  5. 	    x = 0;
  6.     int neg = 0;
  7.  
  8. 	    for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
  9.  
  10. 	    if(c=='-') {
  11. 	        neg = 1;
  12. 	        c = getchar_unlocked();
  13. 	    }
  14.  
  15. 	    for(; c>47 && c<58 ; c = getchar_unlocked()) {
  16. 	        x = (x<<1) + (x<<3) + c - 48;
  17. 	    }
  18.  
  19. 	    if(neg)
  20. 	        x = -x;
  21. 	}
  22. int max(int a,int b)
  23. {
  24.     if(a>b)
  25.         return a;
  26.     return b;
  27. }
  28. int min(int a,int b)
  29. {
  30.     if(a<b)
  31.         return a;
  32.     return b;
  33. }
  34. int main()
  35. {
  36.     int t;
  37.     scanf("%d",&t);
  38.     while(t--){
  39.     int r,c,i,j;
  40.     fastRead_int(r);
  41.     fastRead_int(c);
  42.     //scanf("%d%d",&r,&c);
  43.     int a[r+1][c+1],dp[r+1][c+1],m[r+1][c+1];
  44.     for(i=0;i<r;i++)
  45.     {
  46.         for(j=0;j<c;j++)
  47.         fastRead_int(a[i][j]);
  48.         //scanf("%d",&a[i][j]);
  49.     }
  50.     dp[r-1][c-1]=1;
  51.     for(j=c-2;j>=0;j--)
  52.     {
  53.     	dp[r-1][j]=dp[r-1][j+1]-a[r-1][j];
  54.     	if(dp[r-1][j]<1)
  55.     	dp[r-1][j]=1;
  56.     }
  57.     for(i=r-2;i>=0;i--)
  58.     {
  59.     	dp[i][c-1]=dp[i+1][c-1]-a[i][c-1];
  60.     	if(dp[i][c-1]<1)
  61.     	dp[i][c-1]=1;
  62.     }
  63.     for(i=r-2;i>=0;i--)
  64.     {
  65.     	for(j=c-2;j>=0;j--)
  66.     	{
  67.     		dp[i][j]=(dp[i+1][j]<dp[i][j+1]?dp[i+1][j]:dp[i][j+1])-a[i][j];
  68.     		if(dp[i][j]<1)
  69.     		dp[i][j]=1;
  70.     	}
  71.     }
  72.     printf("%d\n",dp[0][0]);
  73.     }
  74.     return 0;
  75. }
  76.  
  77.  
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0
stdout
copy 
2
1
2
https://ideone.com/dtDpGO
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!