fork download
copy 
  1. //
  2. // Created by Dishant on 16-05-2018.
  3. //
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. /*#include<ext/pb_ds/assoc_container.hpp>
  7. #include<ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9. /*template <typename T>
  10. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. */typedef long long ll;
  12. typedef unsigned long long ull;
  13. typedef long double ld;
  14. typedef pair<ll,ll> pl;
  15. typedef pair<int,int> pii;
  16.  
  17. #define LOCAL 0
  18. #define dbg(x) cout << #x << " is " << x << "\n"
  19. #define gll(x) scanf("%d",&x)
  20. #define gll2(x,y) scanf("%d%d",&x,&y)
  21. #define gll3(x,y,z) scanf("%d%d%d",&x,&y,&y)
  22. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  23. #define sz(x) ((int)x.size())
  24. #define s(x) sort(x.begin(),x.end())
  25. #define all(v) v.begin(),v.end()
  26. #define rs(v) { s(v) ; r(v) ; }
  27. #define r(v) {reverse(all(v));}
  28. #define pb push_back
  29. #define F first
  30. #define S second
  31. #define f(i,n) for(int i=0;i<n;i++)
  32. #define fr(i,n) for(int i=n-1;i>=0;i--)
  33. #define rep(i,a,b) for(int i=a;i<=b;i++)
  34. #define repr(i,a,b) for(int i=a;i>=b;i--)
  35.  
  36. const ll mod = 1000000007;
  37. const ll inf = (ll)1e17;
  38. const ld eps = 1e-12;
  39. const ll N = (int)1e5+5;
  40. const ll LOGN = 19;
  41. const ld PI = 3.14159265358979323846;
  42. ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  43. ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  44. ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  45.  
  46. int main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     if (LOCAL) {
  50.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
  51.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
  52.     }
  53.     int t;
  54.     cin >> t;
  55.     while(t--) {
  56.         int r, c;
  57.         cin >> r >> c;
  58.         int a[r + 2][c + 2];
  59.         ll dp[r + 2][c + 2];            //Stores the maximum value of path from (1,1) -> (r,c)
  60.         ll minimum[r + 2][c + 2];       //Stores the minimum value encountered in path (1,1) -> (r,c)
  61.         rep(i,1,r)
  62.         {
  63.             rep(j,1,c)
  64.                 cin >> a[i][j];
  65.         }
  66.         f(i,r+2)
  67.         {
  68.             f(j,c+2)
  69.             {
  70.                 dp[i][j] = -inf;
  71.                 minimum[i][j] = inf;
  72.             }
  73.         }
  74.         rep(i,1,r)
  75.         {
  76.             rep(j,1,c)
  77.             {
  78.                 if(i == 1 && j == 1)
  79.                     dp[i][j] = a[i][j],minimum[i][j] = a[i][j];
  80.                 else {
  81.                     if(dp[i-1][j] > dp[i][j-1]) {
  82.                         dp[i][j] = dp[i-1][j] + a[i][j];
  83.                         minimum[i][j] = min(dp[i][j],minimum[i-1][j]);
  84.                     }
  85.                     else {
  86.                         dp[i][j] = dp[i][j-1] + a[i][j];
  87.                         minimum[i][j] = min(dp[i][j],minimum[i][j-1]);
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.         assert(minimum[r][c] != inf);
  93.         cout<<1 - minimum[r][c]<<endl;
  94.     }
  95.     return 0;
  96. }
Runtime error #stdin #stdout 0s 4192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7xJACG
language:
C++ (gcc 8.3)
created:
5 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!