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
AC × 4
AC × 10
WA × 1
RE × 4
AC × 23
WA × 4
RE × 7
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