Submission #8423

#	Time	Username	Problem	Language	Result	Execution time	Memory
8423		tncks0121	On grid (kriii2_O)	C++98	4 / 4	44 ms	2140 KiB

O

#include <cstdio>
#include <algorithm>
using namespace std;

int R, C;
int A[300][300], S[300][300];
int Table[300][300];

int sumA (int x1, int y1, int x2, int y2) {
	return S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1];	
}

int main() {
	scanf("%d%d", &R, &C);
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C; j++) {
			scanf("%d", &A[i][j]);
			if(i == 0 && j == 0) S[i][j] = A[i][j];
			else if(i == 0) S[i][j] = S[i][j-1] + A[i][j];
			else if(j == 0) S[i][j] = S[i-1][j] + A[i][j];
			else S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
		}
	}
	
	Table[0][0] = A[0][0];
	for(int i = 1; i < R; i++) Table[i][0] = Table[i-1][0] + A[i][0];
	for(int j = 1; j < C; j++) Table[0][j] = Table[0][j-1] + A[0][j];
	for(int i = 1; i < R; i++) for(int j = 1; j < C; j++) Table[i][j] = sumA(0,0,i,j);
	
	/*for(int i = 1; i < R; i++) for(int j = 1; j < C; j++) {
		int v = sumA(0, 0, i, j);
		for(int h = 1; h <= i; h++) {
			for(int w = 1; w <= j; w++) {
				v = max(v, Table[i-h][j-w] + sumA(i-h+1, j-w+1, i, j));
			}
		}
		Table[i][j] = v;
	}*/
	
	for(int i = 1; i < R; i++) {
		for(int h = 1; h <= i; h++) {
			int now = (int)-2e9;
			for(int j = 1; j < C; j++) {
				now = max(now, Table[i-h][j-1]) + sumA(i-h+1, j, i, j);
				Table[i][j] = max(Table[i][j], now);
			}	
		}
	}
	
	printf("%d\n", Table[R-1][C-1]);
	return 0;
}

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