oj.uz

답안 #16511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16511 2015-08-27T00:22:37 Z hongjun7 On grid (kriii2_O) C++
0 / 4
 1 ms 2172 KB 
#include <stdio.h>
#define MN 305
#define max(a, b) ((a)>(b)?(a):(b))
const int oo = 1e9;
int n, m, x, c[MN][MN], d[MN][MN], f[MN][MN];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &x);
			c[i][j] = x + c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
		}
	}
	for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = -oo;
	for (int j = 1; j <= m; j++) {
		for (int i = n; i >= 1; i--) {
			d[i][j] = c[i][j];
			for (int k = 0; k < i; k++) d[i][j] = max(d[i][j], f[k][i] + c[i][j] - c[k][j]);
			for (int k = i + 1; k <= n; k++) f[i][k] = max(f[i][k], d[i][j] - c[k][j] + c[i][j]);
		}
	}
	printf("%d", d[n][m]);
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2172 KB Output is correct
2 Correct 0 ms 2172 KB Output is correct
3 Correct 0 ms 2172 KB Output is correct
4 Correct 0 ms 2172 KB Output is correct
5 Correct 1 ms 2172 KB Output is correct
6 Correct 0 ms 2172 KB Output is correct
7 Correct 0 ms 2172 KB Output is correct
8 Correct 0 ms 2172 KB Output is correct
9 Correct 0 ms 2172 KB Output is correct
10 Correct 0 ms 2172 KB Output is correct
11 Correct 0 ms 2172 KB Output is correct
12 Incorrect 0 ms 2172 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

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