Submission #9211

#TimeUsernameProblemLanguageResultExecution timeMemory
9211kcm1700On grid (kriii2_O)C++14
4 / 4
48 ms1804 KiB
#include <algorithm>
#include <climits>
#include <cstdio>

using namespace std;

int n,m;
int dat[303][303];
int dt[303][303];
int cursum[303];

int main(){
  scanf("%d%d",&n,&m);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      scanf("%d",&dat[i][j]);
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < m; j++) {
      dt[i][j] = INT_MIN/2;
    }
  }
  for(int i = 0; i < n; i++) {
    for(int k = 0; k < m; k++) cursum[k] = 0;
    for(int j = i; j < n; j++) {
      for(int k = 0; k < m; k++) {
        cursum[k] += dat[j][k];
      }
      int best = INT_MIN/2-10002;
      if (i == 0) best = 0;
      for(int k = 0; k < m; k++) {
        if (k > 0 && i > 0) best = max(best, dt[i][k-1]);
        best += cursum[k];
        dt[j+1][k] = max(dt[j+1][k], best);
      }
    }
  }
  printf("%d\n", dt[n][m-1]);
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...