Submission #9510

#	Time	Username	Problem	Language	Result	Execution time	Memory
9510		ainu7	On grid (kriii2_O)	C++98	0 / 4	0 ms	2736 KiB

O

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int sum[302][302], num[300][300];
int best[300][300];

int main()
{
  int R, C;
  cin >> R >> C;
  for (int i=0; i<R; i++) for (int j=0; j<C; j++) cin >> num[i][j];

  for (int i=0; i<R; i++) for (int j=0; j<C; j++)
    sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + num[i][j];

  for (int i=0; i<C; i++) best[0][i] = sum[1][i+1];
  for (int i=1; i<R; i++) {
    for (int j=0; j<C; j++) best[i][j] = sum[i+1][j+1];
    for (int j=-1; j<i; j++) {
      int last = -999999999;
      for (int k=1; k<C; k++) {
        int nxt1 = last + sum[i+1][k+1] - sum[j+1][k+1] - sum[i+1][k] + sum[j+1][k];
        best[i][k] = max(best[i][k], nxt1);
        last = max(last, nxt1);

        int nxt2 = sum[j+1][k] + sum[i+1][k+1] - sum[j+1][k+1] - sum[i+1][k] + sum[j+1][k];
        best[i][k] = max(best[i][k], nxt2);
        last = max(last, nxt2);
      }
    }
  }
  for (int i=0; i<R; i++) {
//    for (int j=0; j<C; j++) printf("%d ", best[i][j]); printf("\n");
  }

  cout << best[R-1][C-1] << endl;
}

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