Submission #8920

#	Time	Username	Problem	Language	Result	Execution time	Memory
8920		xhae	On grid (kriii2_O)	C++14	1 / 4	1000 ms	1876 KiB

O

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[300][300];
bool isVisited[300][300];
int sum[300][300];
int r, c;

int getSum(int sy, int sx, int ey, int ex)
{
	int ret = sum[ey][ex];
	if(sy > 0) ret -= sum[sy - 1][ex];
	if(sx > 0) ret -= sum[ey][sx - 1];
	if(sy > 0 and sx > 0) ret += sum[sy - 1][sx - 1];
	return ret;
}

int getAns(int y, int x)
{
	if(y == r and x == c) return 0;
	else if(y == r or x == c) return -(1 << 29);
	int &ret = dp[y][x];
	if(isVisited[y][x]) return ret;
	isVisited[y][x] = true;

	ret = -(1 << 29);
	for(int cy = y; cy < r; cy++)
		for(int cx = x; cx < c; cx++)
			ret = max(ret, getAns(cy + 1, cx + 1) + getSum(y, x, cy, cx));
	return ret;
}

int main(void)
{
	scanf("%d %d", &r, &c);
	for(int i = 0; i < r; i++) 
		for(int j = 0; j < c; j++) 
		{
			int &s = sum[i][j];
			scanf("%d", &s);
			if(i > 0) s += sum[i - 1][j];
			if(j > 0) s += sum[i][j - 1];
			if(i > 0 and j > 0) s -= sum[i - 1][j - 1];
		}

	printf("%d\n", getAns(0, 0));
	return 0;
}

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