oj.uz

Submission #9710

# Submission time Handle Problem Language Result Execution time Memory
9710 2014-09-28T08:17:39 Z silas On grid (kriii2_O) C++
1 / 4
 1000 ms 2392 KB 
#include <iostream>
#include <vector>
#include <string.h>
#define INF -987654321
using namespace std;

int R, C;
int  arr[303][303];
int  cache[303][303];

int psum_element(int y, int x, int val) {
	int ret = val;
	if (x - 1 >= 1) {
		ret += arr[y][x-1];
	}
	if (y - 1 >= 1) {
		ret += arr[y-1][x];
	}
	if (x - 1 >= 1 && y - 1>= 1)
		ret -= arr[y-1][x-1];
	return ret;
}

int area_sum(int ori_y, int ori_x, int sub_y, int sub_x) {
	int ret = 0;
	ret += arr[ori_y][ori_x];
	ret -= arr[ori_y][sub_x];
	ret -= arr[sub_y][ori_x];
	ret += arr[sub_y][sub_x];
	return ret;
}

int dp (int y, int x) {
	if (y == 0 || x == 0)
		return INF;
	if (y == 1)
		return arr[1][x];
	if (x == 1)
		return arr[y][1];
	int  &ret = cache[y][x];
	if (ret != -1)
		return ret;
	ret = INF;
	for (int i = y - 1; i >= 0; i--) {
		for (int j = x - 1; j >= 0; j--) {
			if (cache[i][j] != -1)
				ret = max(ret, cache[i][j] + area_sum(y, x, i, j));
			else 
				ret = max(ret, dp(i, j) + area_sum(y, x, i, j));
		}
	}
	ret = max(ret, arr[y][x]);
	return ret;
}

int main() {
	cin >> R >> C;
	memset(cache, -1, sizeof(cache));
	int temp;
	for (int i = 1 ; i <= R; i++) {
		for (int j = 1 ; j <= C; j++) {
			cin >> temp;
			arr[i][j] = psum_element(i, j, temp);
		}
	} // psum 2차원 배열을 완성
	cout << dp(R, C) << endl;


	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2392 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 0 ms 2392 KB Output is correct
15 Correct 0 ms 2392 KB Output is correct
16 Correct 0 ms 2392 KB Output is correct
17 Correct 0 ms 2392 KB Output is correct
18 Correct 0 ms 2392 KB Output is correct
19 Correct 0 ms 2392 KB Output is correct
20 Correct 0 ms 2392 KB Output is correct
21 Correct 0 ms 2392 KB Output is correct
22 Correct 0 ms 2392 KB Output is correct
23 Correct 0 ms 2392 KB Output is correct
24 Correct 0 ms 2392 KB Output is correct
25 Correct 0 ms 2392 KB Output is correct
26 Correct 0 ms 2392 KB Output is correct
27 Correct 0 ms 2392 KB Output is correct
28 Correct 0 ms 2392 KB Output is correct
29 Correct 0 ms 2392 KB Output is correct
30 Correct 0 ms 2392 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 2392 KB Output is correct
2 Correct 200 ms 2392 KB Output is correct
3 Correct 844 ms 2392 KB Output is correct
4 Correct 476 ms 2392 KB Output is correct
5 Correct 224 ms 2392 KB Output is correct
6 Execution timed out 1000 ms 2392 KB Program timed out
7 Halted 0 ms 0 KB -