Submission #2528223


Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;
using vector2D = vector< vector<ll> >;
const long long int INF = 1LL << 60;

vector2D rotate(vector2D board) {
    int N = board.size(), M = board[0].size();
    vector2D ret(M, vector<ll>(N));

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            ret[j][i] = board[i][j];
        }
    }
    return ret;
}

long long int solve(vector2D board) {
    int N = board.size(), M = board[0].size();
    vector2D sum(N, vector<ll>(M+1));
    vector<ll> left(M+1, -INF), right(M+1, -INF);
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            sum[i][j+1] = sum[i][j] + board[i][j];
        }
    }

    for(int l=0; l<M; l++) {
        for(int r=l+1; r<=M; r++) {
            ll mi = 0, ma = -INF, s = 0;
            for(int h=0; h<N; h++) {
                ll val = sum[h][r] - sum[h][l] + s;
                ma = max(ma, val - mi);
                mi = min(mi, val);
                s = val;
            }

            for(int i=r; i<=M; i++) {
                left[i] = max(left[i], ma);
            }
            for(int i=0; i<=l; i++) {
                right[i] = max(right[i], ma);
            }
        }
    }

    ll ret = -INF;
    for(int i=0; i<=M; i++) {
        ret = max(ret, left[i] + right[i]);
    }
    return ret;
}

int main() {
    int H, W; scanf("%d%d", &H, &W);
    vector2D board(H, vector<ll>(W));
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            scanf("%lld", &board[i][j]);
        }
    }

    long long int ans = -INF;
    ans = max(ans, solve(board));
    board = rotate(board);
    ans = max(ans, solve(board));
    printf("%lld\n", ans);
    return 0;
}

Submission Info

Submission Time
Task D - 庭園
User tsutaj
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1821 Byte
Status AC
Exec Time 102 ms
Memory 2192 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int H, W; scanf("%d%d", &H, &W);
                                    ^
./Main.cpp:62:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &board[i][j]);
                                        ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 4
AC × 15
AC × 34
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 256 KB
subtask0_1.txt AC 2 ms 256 KB
subtask0_10.txt AC 2 ms 256 KB
subtask0_11.txt AC 2 ms 256 KB
subtask0_12.txt AC 2 ms 256 KB
subtask0_13.txt AC 2 ms 256 KB
subtask0_14.txt AC 2 ms 256 KB
subtask0_2.txt AC 2 ms 256 KB
subtask0_3.txt AC 2 ms 256 KB
subtask0_4.txt AC 2 ms 256 KB
subtask0_5.txt AC 2 ms 256 KB
subtask0_6.txt AC 2 ms 256 KB
subtask0_7.txt AC 2 ms 256 KB
subtask0_8.txt AC 2 ms 256 KB
subtask0_9.txt AC 2 ms 256 KB
subtask1_0.txt AC 77 ms 1920 KB
subtask1_1.txt AC 102 ms 2048 KB
subtask1_10.txt AC 72 ms 1792 KB
subtask1_11.txt AC 94 ms 2192 KB
subtask1_12.txt AC 81 ms 1936 KB
subtask1_13.txt AC 100 ms 2176 KB
subtask1_14.txt AC 76 ms 1952 KB
subtask1_2.txt AC 92 ms 2076 KB
subtask1_3.txt AC 74 ms 1920 KB
subtask1_4.txt AC 81 ms 1920 KB
subtask1_5.txt AC 90 ms 2084 KB
subtask1_6.txt AC 86 ms 2048 KB
subtask1_7.txt AC 82 ms 1932 KB
subtask1_8.txt AC 97 ms 2176 KB
subtask1_9.txt AC 83 ms 2036 KB