답안 #9827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9827 2014-09-28T12:49:16 Z veckal On grid (kriii2_O) C++14
4 / 4
464 ms 107612 KB
#include<stdio.h>
#include<string.h>

int r, c, grid[300][300], psum[300][300];
int cache[300][300], reCache[300][300][300];

inline int max(int a, int b) {
	return (a>b)?a:b;
}

int reverseGrid(int, int, int);

int onGrid(int y, int x) {
	int &ret = cache[y][x];
	if (~ret) return ret;
	ret = psum[y][x];
	if (!y || !x) return ret;
	for (int h=0; h<y; ++h)
		ret = max(ret, reverseGrid(y, x-1, h) + psum[y][x] - psum[h][x] - psum[y][x-1] + psum[h][x-1]);
	return ret;
}

int reverseGrid(int y, int x, int h) {
	int &ret = reCache[y][x][h];
	if (~ret) return ret;
	ret = onGrid(h, x);
	if (x == 0) return ret;
	int smallGrid = psum[y][x] - psum[h][x] - psum[y][x-1] + psum[h][x-1];
	ret = max(ret, reverseGrid(y, x-1, h) + smallGrid);
	ret = max(ret, onGrid(h, x-1) + smallGrid);
	return ret;
}

int main() {
	scanf("%d%d", &r, &c);
	for (int i=0; i<r; ++i)
		for (int j=0; j<c; ++j)
			scanf("%d", grid[i]+j);
	psum[0][0] = grid[0][0];
	for (int i=1; i<c; ++i)
		psum[0][i] = psum[0][i-1] + grid[0][i];
	for (int i=1; i<r; ++i) {
		psum[i][0] = grid[i][0] + psum[i-1][0];
		for (int j=1; j<c; ++j)
			psum[i][j] = psum[i][j-1] + psum[i-1][j] + grid[i][j] - psum[i-1][j-1];
	}
	memset(cache, -1, sizeof cache);
	memset(reCache, -1, sizeof reCache);
	printf("%d\n", onGrid(r-1, c-1));
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 107612 KB Output is correct
2 Correct 24 ms 107612 KB Output is correct
3 Correct 12 ms 107612 KB Output is correct
4 Correct 24 ms 107612 KB Output is correct
5 Correct 24 ms 107612 KB Output is correct
6 Correct 28 ms 107612 KB Output is correct
7 Correct 20 ms 107612 KB Output is correct
8 Correct 36 ms 107612 KB Output is correct
9 Correct 20 ms 107612 KB Output is correct
10 Correct 24 ms 107612 KB Output is correct
11 Correct 24 ms 107612 KB Output is correct
12 Correct 20 ms 107612 KB Output is correct
13 Correct 28 ms 107612 KB Output is correct
14 Correct 28 ms 107612 KB Output is correct
15 Correct 24 ms 107612 KB Output is correct
16 Correct 16 ms 107612 KB Output is correct
17 Correct 24 ms 107612 KB Output is correct
18 Correct 0 ms 107612 KB Output is correct
19 Correct 32 ms 107612 KB Output is correct
20 Correct 40 ms 107612 KB Output is correct
21 Correct 12 ms 107612 KB Output is correct
22 Correct 28 ms 107612 KB Output is correct
23 Correct 24 ms 107612 KB Output is correct
24 Correct 28 ms 107612 KB Output is correct
25 Correct 28 ms 107612 KB Output is correct
26 Correct 20 ms 107612 KB Output is correct
27 Correct 40 ms 107612 KB Output is correct
28 Correct 20 ms 107612 KB Output is correct
29 Correct 20 ms 107612 KB Output is correct
30 Correct 24 ms 107612 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 107612 KB Output is correct
2 Correct 60 ms 107612 KB Output is correct
3 Correct 208 ms 107612 KB Output is correct
4 Correct 136 ms 107612 KB Output is correct
5 Correct 60 ms 107612 KB Output is correct
6 Correct 188 ms 107612 KB Output is correct
7 Correct 116 ms 107612 KB Output is correct
8 Correct 268 ms 107612 KB Output is correct
9 Correct 452 ms 107612 KB Output is correct
10 Correct 448 ms 107612 KB Output is correct
11 Correct 140 ms 107612 KB Output is correct
12 Correct 140 ms 107612 KB Output is correct
13 Correct 88 ms 107612 KB Output is correct
14 Correct 368 ms 107612 KB Output is correct
15 Correct 144 ms 107612 KB Output is correct
16 Correct 92 ms 107612 KB Output is correct
17 Correct 228 ms 107612 KB Output is correct
18 Correct 188 ms 107612 KB Output is correct
19 Correct 200 ms 107612 KB Output is correct
20 Correct 68 ms 107612 KB Output is correct
21 Correct 88 ms 107612 KB Output is correct
22 Correct 68 ms 107612 KB Output is correct
23 Correct 80 ms 107612 KB Output is correct
24 Correct 424 ms 107612 KB Output is correct
25 Correct 72 ms 107612 KB Output is correct
26 Correct 48 ms 107612 KB Output is correct
27 Correct 360 ms 107612 KB Output is correct
28 Correct 172 ms 107612 KB Output is correct
29 Correct 104 ms 107612 KB Output is correct
30 Correct 96 ms 107612 KB Output is correct
31 Correct 164 ms 107612 KB Output is correct
32 Correct 444 ms 107612 KB Output is correct
33 Correct 236 ms 107612 KB Output is correct
34 Correct 92 ms 107612 KB Output is correct
35 Correct 128 ms 107612 KB Output is correct
36 Correct 464 ms 107612 KB Output is correct
37 Correct 96 ms 107612 KB Output is correct
38 Correct 96 ms 107612 KB Output is correct
39 Correct 92 ms 107612 KB Output is correct
40 Correct 76 ms 107612 KB Output is correct