Submission #2489465
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;
void main() {
immutable long INF = 1L << 59;
auto s = readln.split.map!(to!int);
auto H = s[0];
auto W = s[1];
auto A = H.iota.map!(_ => readln.split.map!(to!long).array).array;
auto B = new long[][](H+1, W+1);
foreach (i; 0..H) foreach (j; 0..W) B[i+1][j+1] = B[i+1][j] + A[i][j];
foreach (j; 0..W) foreach (i; 0..H) B[i+1][j+1] += B[i][j+1];
long acm(int r1, int c1, int r2, int c2) {
return B[r2+1][c2+1] - B[r2+1][c1] - B[r1][c2+1] + B[r1][c1];
}
auto dpH = new long[][](H, H);
auto dpW = new long[][](W, W);
auto tmp = new long[](max(H, W) + 1);
foreach (i; 0..H) dpH[i].fill(-INF);
foreach (i; 0..W) dpW[i].fill(-INF);
foreach (r1; 0..H) {
foreach (r2; r1..H) {
tmp.fill(0);
foreach (j; 0..W) {
tmp[j+1] = acm(r1, 0, r2, j);
}
long mn = 0;
foreach (j; 0..W) {
dpH[r1][r2] = max(dpH[r1][r2], tmp[j+1] - mn);
mn = min(mn, tmp[j+1]);
}
}
}
foreach (c1; 0..W) {
foreach (c2; c1..W) {
tmp.fill(0);
foreach (j; 0..H) {
tmp[j+1] = acm(0, c1, j, c2);
}
long mn = 0;
foreach (j; 0..H) {
dpW[c1][c2] = max(dpW[c1][c2], tmp[j+1] - mn);
mn = min(mn, tmp[j+1]);
}
}
}
auto dpH2 = new long[][](H, H);
auto dpW2 = new long[][](W, W);
foreach (i; 0..H) dpH2[i].fill(-INF);
foreach (i; 0..W) dpW2[i].fill(-INF);
foreach (r1; 0..H) {
dpH2[r1][r1] = dpH[r1][r1];
foreach (r2; r1+1..H) {
dpH2[r1][r2] = max(dpH2[r1][r2-1], dpH[r1][r2]);
}
}
foreach (c1; 0..W) {
dpW2[c1][c1] = dpW[c1][c1];
foreach (c2; c1+1..H) {
dpW2[c1][c2] = max(dpW2[c1][c2-1], dpW[c1][c2]);
}
}
long ans = -INF;
foreach (r1; 0..H) foreach (r2; r1+1..H) ans = max(ans, dpH2[r1][r2-1] + dpH2[r2][H-1]);
foreach (c1; 0..W) foreach (c2; c1+1..W) ans = max(ans, dpW2[c1][c2-1] + dpW2[c2][H-1]);
ans.writeln;
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
nebukuro09 |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
2435 Byte |
Status |
RE |
Exec Time |
221 ms |
Memory |
8956 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 50 |
0 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask1 |
subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt |
All |
sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample0.txt |
AC |
1 ms |
256 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |
subtask0_0.txt |
AC |
2 ms |
508 KB |
subtask0_1.txt |
AC |
2 ms |
508 KB |
subtask0_10.txt |
AC |
2 ms |
508 KB |
subtask0_11.txt |
AC |
2 ms |
508 KB |
subtask0_12.txt |
RE |
2 ms |
508 KB |
subtask0_13.txt |
RE |
2 ms |
508 KB |
subtask0_14.txt |
AC |
2 ms |
508 KB |
subtask0_2.txt |
RE |
3 ms |
508 KB |
subtask0_3.txt |
AC |
2 ms |
508 KB |
subtask0_4.txt |
AC |
2 ms |
508 KB |
subtask0_5.txt |
RE |
2 ms |
508 KB |
subtask0_6.txt |
AC |
2 ms |
508 KB |
subtask0_7.txt |
AC |
2 ms |
508 KB |
subtask0_8.txt |
WA |
2 ms |
508 KB |
subtask0_9.txt |
AC |
2 ms |
508 KB |
subtask1_0.txt |
WA |
175 ms |
5372 KB |
subtask1_1.txt |
AC |
203 ms |
5628 KB |
subtask1_10.txt |
RE |
161 ms |
7676 KB |
subtask1_11.txt |
AC |
209 ms |
8956 KB |
subtask1_12.txt |
AC |
182 ms |
6652 KB |
subtask1_13.txt |
WA |
213 ms |
8188 KB |
subtask1_14.txt |
RE |
169 ms |
7548 KB |
subtask1_2.txt |
AC |
206 ms |
8700 KB |
subtask1_3.txt |
WA |
166 ms |
7676 KB |
subtask1_4.txt |
AC |
183 ms |
8444 KB |
subtask1_5.txt |
AC |
210 ms |
8060 KB |
subtask1_6.txt |
RE |
196 ms |
8316 KB |
subtask1_7.txt |
AC |
184 ms |
7548 KB |
subtask1_8.txt |
AC |
221 ms |
8572 KB |
subtask1_9.txt |
AC |
179 ms |
5372 KB |