oj.uz

답안 #18138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18138 2016-01-24T07:24:31 Z tlwpdus On grid (kriii2_O) C++
1 / 4
 1000 ms 2208 KB 
#include<stdio.h>
#include<algorithm>

using namespace std;

int r, c;
int map[310][310];
int psum[310][310];
int dyn[310][310];

void process() {
	int i, j, k, l, maxi;
	for (i=0;i<r;i++) for (j=0;j<c;j++) {
		if (i==0&&j==0) psum[i][j] = map[i][j];
		else if (i==0) psum[i][j] = psum[i][j-1]+map[i][j];
		else if (j==0) psum[i][j] = psum[i-1][j]+map[i][j];
		else psum[i][j] = psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+map[i][j];
	}
	for (i=0;i<r;i++) for (j=0;j<c;j++) {
		if (i==0||j==0) dyn[i][j] = psum[i][j];
		else {
			maxi = psum[i][j];
			for (k=0;k<i;k++) for (l=0;l<j;l++) {
				maxi = max(maxi,dyn[k][l]+psum[i][j]-psum[k][j]-psum[i][l]+psum[k][l]);
			}
			dyn[i][j] = maxi;
		}
	}
	printf("%d\n",dyn[r-1][c-1]);
}

void input() {
	int i, j;
	scanf("%d %d",&r,&c);
	for (i=0;i<r;i++) {
		for (j=0;j<c;j++) {
			scanf("%d",&map[i][j]);
		}
	}
}

int main() {
	input();
	process();
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 2208 KB Output is correct
2 Correct 132 ms 2208 KB Output is correct
3 Correct 568 ms 2208 KB Output is correct
4 Correct 315 ms 2208 KB Output is correct
5 Correct 148 ms 2208 KB Output is correct
6 Execution timed out 1000 ms 2208 KB Program timed out
7 Halted 0 ms 0 KB -