Submission #8919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
8919	2014-09-25T06:15:25 Z	xhae	On grid (kriii2_O)	C++14	0 / 4	0 ms	1876 KB

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 << 30);
	int &ret = dp[y][x];
	if(isVisited[y][x]) return ret;
	isVisited[y][x] = true;

	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

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1876 KB	Output is correct
2	Correct	0 ms	1876 KB	Output is correct
3	Correct	0 ms	1876 KB	Output is correct
4	Incorrect	0 ms	1876 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-