fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define PB push_back
  3. #define MP make_pair
  4. #define F first
  5. #define S second
  6. #define loop(i,a,b) for(int i=a;i<b;i++)
  7. #define si(n) scanf("%d",&n)
  8. #define sll(n) scanf("%lld",&n)
  9. using namespace std;
  10. typedef pair<int,int> ii;
  11. typedef vector<int> vi;
  12. typedef vector< vi > vvi;
  13. typedef vector< ii > vii;
  14. //***********************************END OF TEMPLATE*********************************************************************
  15. int a[502][502];
  16. ii dp[502][502];          //dp[r][c].F => Min power to reach {r,c}
  17. 			 //dp[r][c].S => total power till {r,c} when optimal path followed
  18. ii solve(int r,int c){
  19. 	if(r<0||c<0)
  20. 		return {1e7,1e7};
  21. 	//base case
  22. 	if(r==0&&c==0){
  23. 		if(a[r][c] == 0)
  24. 			return {1,1};
  25. 		else if(a[r][c]>0)
  26. 			return {0,a[r][c]};
  27. 		else if(a[r][c]<0)
  28. 			return {abs(a[0][0])+1,1};
  29. 	}
  30. 	if(dp[r][c].F!=-1)
  31. 		return dp[r][c];
  32. 	//Recursion
  33. 	ii up = solve(r-1,c);
  34. 	ii left = solve(r,c-1);
  35. 	if(up.S+a[r][c]<=0){
  36. 		up.F += abs(up.S+a[r][c])+1;
  37. 		up.S += abs(up.S+a[r][c])+1;
  38. 	}
  39. 	if(left.S+a[r][c]<=0){
  40. 		left.F += abs(left.S+a[r][c])+1;
  41. 		left.S += abs(left.S+a[r][c])+1;
  42. 	}
  43. 	if(left.F<up.F)
  44. 		dp[r][c] =  {left.F,left.S+a[r][c]};
  45. 	else if(up.F<left.F)
  46. 		dp[r][c] = {up.F,up.S+a[r][c]};
  47. 	else if(up.F==left.F)
  48. 		dp[r][c] = {up.F,a[r][c]+max(up.S,left.S)};
  49. 	return dp[r][c];
  50. }
  51. int main(){
  52. 	int t;
  53. 	int r,c;
  54. 	si(t);
  55. 	while(t--){
  56. 		si(r);si(c);
  57. 		loop(i,0,r){
  58. 			loop(j,0,c){
  59. 				si(a[i][j]);
  60. 				dp[i][j].F=-1;
  61. 			}
  62. 		}
  63. 		ii ans = solve(r-1,c-1);
  64. 		/*loop(i,0,r){
  65. 			loop(j,0,c){
  66. 				printf("%d ",dp[i][j].F);
  67. 			}
  68. 			printf("\n");
  69. 		}*/
  70. 		printf("%d\n",ans.F);
  71. 	}
  72. 	return 0;
  73. }
Runtime error #stdin #stdout 0.18s 6412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tLIrsZ
language:
C++14 (gcc 8.3)
created:
8 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!