oj.uz

답안 #8919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8919 2014-09-25T06:15:25 Z xhae On grid (kriii2_O) C++14
0 / 4
 0 ms 1876 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -