oj.uz

답안 #8420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8420 2014-09-13T17:59:34 Z tncks0121 On grid (kriii2_O) C++
0 / 4
 0 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 = (int)-2e9;
		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
0.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 Incorrect 0 ms 2140 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

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