#include <cstdio>
#include <iostream>
#include <cstring>
#include <tuple>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i=0; i < n; ++i)
int n, m;
int a[305][305];
long long S[305][305];
long long V[305][305];
long long C[305][305];
long long M[305][305][305];
long long compute_M(int i, int j, int k) {
if(j == 1) {
int l = 0;
return C[k][l] - S[i][l] - S[k][j] + S[k][l];
}
else {
long long left = M[i][j - 1][k] - S[k][j] + S[k][j - 1];
int l = j - 1;
long long right = C[k][l] - S[i][l] - S[k][j] + S[k][l];
return max(left, right);
}
}
long long go() {
memset(C, 0, sizeof(C));
memset(M, 0, sizeof(M));
memset(V, 0, sizeof(V));
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= m; ++ j) {
S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
}
}
const long long INF = 1LL << 50;
for(int i = 1; i <= n; ++ i) {
V[i][0] = -INF;
C[i][0] = -INF;
}
for(int j = 1; j <= m; ++ j) {
V[0][j] = -INF;
C[0][j] = -INF;
}
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= m; ++ j) {
// M[i][j] = max { C[k][l] - S[i][l] - S[k][j] + S[k][] }
// k < i, l < j
// M[i][j-1] = max { C[k][l] - S[i][l] - S[k][j] + S[k][l] }
// k < i, l < j-1
long long maxi = 0;
for(int k = 0; k < i; ++ k) {
M[i][j][k] = compute_M(i, j, k);
// printf("M %d %d %d = %lld\n", i, j, k, M[i][j][k]);
maxi = max(maxi, M[i][j][k]);
}
C[i][j] = maxi + S[i][j];
/*
V[i][j] = -INF;
for(int k = 0; k < i; ++ k) {
for(int l = 0; l < j; ++ l) {
V[i][j] = max(V[i][j], V[k][l] - S[i][l] - S[k][j] + S[k][l] + S[i][j]);
}
}
*/
// printf("[%3lld]<%3lld> / %2lld+%2lld ", C[i][j], V[i][j], S[i][j], maxi);
}
// printf("\n");
}
return C[n][m];
}
int main() {
while(cin >> n >> m && n && m ) {
for(int i = 1; i <= n; ++ i) {
for(int j=1; j<=m; ++j) {
cin >> a[i][j];
}
}
cout << go() << endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
56 ms |
225880 KB |
Output is correct |
| 2 |
Correct |
56 ms |
225880 KB |
Output is correct |
| 3 |
Correct |
40 ms |
225880 KB |
Output is correct |
| 4 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 5 |
Correct |
56 ms |
225880 KB |
Output is correct |
| 6 |
Correct |
48 ms |
225880 KB |
Output is correct |
| 7 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 8 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 9 |
Correct |
28 ms |
225880 KB |
Output is correct |
| 10 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 11 |
Correct |
48 ms |
225880 KB |
Output is correct |
| 12 |
Correct |
60 ms |
225880 KB |
Output is correct |
| 13 |
Correct |
36 ms |
225880 KB |
Output is correct |
| 14 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 15 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 16 |
Correct |
36 ms |
225880 KB |
Output is correct |
| 17 |
Correct |
68 ms |
225880 KB |
Output is correct |
| 18 |
Correct |
52 ms |
225880 KB |
Output is correct |
| 19 |
Correct |
56 ms |
225880 KB |
Output is correct |
| 20 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 21 |
Correct |
92 ms |
225880 KB |
Output is correct |
| 22 |
Correct |
52 ms |
225880 KB |
Output is correct |
| 23 |
Correct |
48 ms |
225880 KB |
Output is correct |
| 24 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 25 |
Correct |
52 ms |
225880 KB |
Output is correct |
| 26 |
Correct |
32 ms |
225880 KB |
Output is correct |
| 27 |
Correct |
52 ms |
225880 KB |
Output is correct |
| 28 |
Correct |
44 ms |
225880 KB |
Output is correct |
| 29 |
Correct |
32 ms |
225880 KB |
Output is correct |
| 30 |
Correct |
48 ms |
225880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 2 |
Correct |
68 ms |
225880 KB |
Output is correct |
| 3 |
Correct |
112 ms |
225880 KB |
Output is correct |
| 4 |
Correct |
100 ms |
225880 KB |
Output is correct |
| 5 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 6 |
Correct |
112 ms |
225880 KB |
Output is correct |
| 7 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 8 |
Correct |
92 ms |
225880 KB |
Output is correct |
| 9 |
Correct |
164 ms |
225880 KB |
Output is correct |
| 10 |
Correct |
176 ms |
225880 KB |
Output is correct |
| 11 |
Correct |
96 ms |
225880 KB |
Output is correct |
| 12 |
Correct |
84 ms |
225880 KB |
Output is correct |
| 13 |
Correct |
68 ms |
225880 KB |
Output is correct |
| 14 |
Correct |
160 ms |
225880 KB |
Output is correct |
| 15 |
Correct |
84 ms |
225880 KB |
Output is correct |
| 16 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 17 |
Correct |
100 ms |
225880 KB |
Output is correct |
| 18 |
Correct |
92 ms |
225880 KB |
Output is correct |
| 19 |
Correct |
92 ms |
225880 KB |
Output is correct |
| 20 |
Correct |
76 ms |
225880 KB |
Output is correct |
| 21 |
Correct |
68 ms |
225880 KB |
Output is correct |
| 22 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 23 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 24 |
Correct |
144 ms |
225880 KB |
Output is correct |
| 25 |
Correct |
56 ms |
225880 KB |
Output is correct |
| 26 |
Correct |
84 ms |
225880 KB |
Output is correct |
| 27 |
Correct |
144 ms |
225880 KB |
Output is correct |
| 28 |
Correct |
92 ms |
225880 KB |
Output is correct |
| 29 |
Correct |
64 ms |
225880 KB |
Output is correct |
| 30 |
Correct |
48 ms |
225880 KB |
Output is correct |
| 31 |
Correct |
96 ms |
225880 KB |
Output is correct |
| 32 |
Correct |
180 ms |
225880 KB |
Output is correct |
| 33 |
Correct |
124 ms |
225880 KB |
Output is correct |
| 34 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 35 |
Correct |
68 ms |
225880 KB |
Output is correct |
| 36 |
Correct |
184 ms |
225880 KB |
Output is correct |
| 37 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 38 |
Correct |
72 ms |
225880 KB |
Output is correct |
| 39 |
Correct |
80 ms |
225880 KB |
Output is correct |
| 40 |
Correct |
72 ms |
225880 KB |
Output is correct |
