SHARE
TWEET

Untitled

a guest Nov 14th, 2017 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int memo[110][110];
  6. int mark[110][110];
  7. int MAXINT = 0x3F3F3F3F;
  8. int N, M;
  9. int grid[110][110];
  10.  
  11. int DP(int i, int j, int sum) {
  12.  if(i >= N || j >= M) return MAXINT;
  13.  if(i < 0) return MAXINT;
  14.  int &best = memo[i][j];
  15.  if((sum+grid[i][j])>best) return MAXINT;
  16.  sum += grid[i][j];
  17.  best=min(DP(i-1, j+1, sum), min(DP(i, j+1, sum), DP(i+1, j+1, sum)));
  18.  return best;
  19. }
  20.  
  21. int main() {
  22.   int i, j;
  23.   cin >> N >> M;
  24.   for (i=0; i<M; i++) {
  25.     for(j=0; j<N; j++) {
  26.       cin >> grid[j][i];
  27.     }
  28.   }
  29.   int sol=0, temp=0;
  30.  
  31.   memset(memo, MAXINT, sizeof(memo));
  32.  
  33.   for(i=0; i<N; i++) {
  34.     temp=DP(i, 0, 0);
  35.     if(sol<temp) sol=temp;
  36.   }
  37.   cout << sol << endl;
  38. }
RAW Paste Data
Top