oj.uz

답안 #8421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8421 2014-09-13T18:02:53 Z tncks0121 On grid (kriii2_O) C++
1 / 4
 1000 ms 2140 KB 
#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++) {
		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;
	}
	
	printf("%d\n", Table[R-1][C-1]);
	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2140 KB Output is correct
2 Correct 0 ms 2140 KB Output is correct
3 Correct 0 ms 2140 KB Output is correct
4 Correct 0 ms 2140 KB Output is correct
5 Correct 0 ms 2140 KB Output is correct
6 Correct 0 ms 2140 KB Output is correct
7 Correct 0 ms 2140 KB Output is correct
8 Correct 0 ms 2140 KB Output is correct
9 Correct 0 ms 2140 KB Output is correct
10 Correct 0 ms 2140 KB Output is correct
11 Correct 0 ms 2140 KB Output is correct
12 Correct 0 ms 2140 KB Output is correct
13 Correct 0 ms 2140 KB Output is correct
14 Correct 0 ms 2140 KB Output is correct
15 Correct 0 ms 2140 KB Output is correct
16 Correct 0 ms 2140 KB Output is correct
17 Correct 0 ms 2140 KB Output is correct
18 Correct 0 ms 2140 KB Output is correct
19 Correct 0 ms 2140 KB Output is correct
20 Correct 0 ms 2140 KB Output is correct
21 Correct 0 ms 2140 KB Output is correct
22 Correct 0 ms 2140 KB Output is correct
23 Correct 0 ms 2140 KB Output is correct
24 Correct 0 ms 2140 KB Output is correct
25 Correct 0 ms 2140 KB Output is correct
26 Correct 0 ms 2140 KB Output is correct
27 Correct 0 ms 2140 KB Output is correct
28 Correct 0 ms 2140 KB Output is correct
29 Correct 0 ms 2140 KB Output is correct
30 Correct 0 ms 2140 KB Output is correct

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 464 ms 2140 KB Output is correct
2 Correct 172 ms 2140 KB Output is correct
3 Correct 744 ms 2140 KB Output is correct
4 Correct 412 ms 2140 KB Output is correct
5 Correct 192 ms 2140 KB Output is correct
6 Execution timed out 1000 ms 2140 KB Program timed out
7 Halted 0 ms 0 KB -