Submission #9211

#	Time	Username	Problem	Language	Result	Execution time	Memory
9211		kcm1700	On grid (kriii2_O)	C++14	4 / 4	48 ms	1804 KiB

O

#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;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3