Submission #9643

#	Time	Username	Problem	Language	Result	Execution time	Memory
9643		jaehadad	On grid (kriii2_O)	C++14	1 / 4	1000 ms	2812 KiB

O

#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int board[300][300];
bool seen[300][300];
int c[300][300];
int partial[300][300];

int rows, cols;
int psum(int y1, int y2, int x1, int x2) {
  int ret = partial[y2][x2];
  if(y1) ret -= partial[y1-1][x2];
  if(x1) ret -= partial[y2][x1-1];
  if(y1 && x1) ret += partial[y1-1][x1-1];
  return ret;
}
int go(int y, int x) {
  if(y == -1 && x == -1) return 0;
  if(y == -1 || x == -1) return -987654321;
  int& ret = c[y][x];
  if(seen[y][x]) return ret;
  seen[y][x] = true;
  ret = -987654321;
  for(int h = 1; h <= y+1; ++h)
    for(int w = 1; w <= x+1; ++w) {
      ret = max(ret,
                psum(y - h + 1, y, x - w + 1, x) + go(y - h, x - w));
    }
  // printf("go(%d,%d) = %d\n", y, x, ret);
  return ret;
}
int main() {
  cin.sync_with_stdio(false);
  cin >> rows >> cols;
  memset(partial, 0, sizeof(partial)); 
  for(int i = 0; i < rows; ++i) {
    for(int j = 0; j < cols; ++j) {
      cin >> board[i][j];
      partial[i][j] = board[i][j];
      if(i > 0) partial[i][j] += partial[i-1][j];
      if(j > 0) partial[i][j] += partial[i][j-1];
      if(i && j) partial[i][j] -= partial[i-1][j-1];
      // printf("%d ", partial[i][j]);
    }
    // printf("\n");
  }
  memset(seen, 0, sizeof(seen)); 
  cout << go(rows-1, cols-1) << endl;
}

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