| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 9421 | silas | On grid (kriii2_O) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#define INF -987654321
using namespace std;
int R, C;
int arr[301][301];
int cache[301][301];
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 = 0;
for (int i = y; i >= 1; i--) {
for (int j = x; j >= 1; j--) {
ret = max(ret, dp(i - 1, j - 1) + area_sum(y, x, i - 1, j - 1));
}
}
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;
}