73312024-01-07 17:24:22Error42Táblatöréscpp17Accepted 50/5012ms7592 KiB
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int prefix[31][31];
// il, ir, jl, jr
int dp[31][31][31][31];

int solve(int const il, int const ir, int const jl, int const jr) {
    if (ir - il == -1 || jr - jl == -1) {
        return 0;
    }

    int& ans = dp[il][ir][jl][jr];

    if (ans != 0) {
        return ans;
    }

    auto const sum = [&](int const il, int const ir, int const jl, int const jr) {
        return prefix[ir + 1][jr + 1] - prefix[il][jr + 1] - prefix[ir + 1][jl] + prefix[il][jl];
    };

    auto const opponent = [&](int const il, int const ir, int const jl, int const jr) {
        return sum(il, ir, jl, jr) - solve(il, ir, jl, jr);
    };

    int const top = opponent(il + 1, ir, jl, jr) + sum(il, il, jl, jr);
    int const bottom = opponent(il, ir - 1, jl, jr) + sum(ir, ir, jl, jr);
    int const left = opponent(il, ir, jl + 1, jr) + sum(il, ir, jl, jl);
    int const right = opponent(il, ir, jl, jr - 1) + sum(il, ir, jr, jr);

    return ans = max({ top, bottom, left, right });
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    prefix[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + a[i][j];
        }
    }

    int const ans = solve(0, n - 1, 0, m - 1);

    cout << ans << "\n";

    //for (int isize = n; isize >= 1; isize--) {
    //    for (int jsize = n; jsize >= 1; jsize--) {
    //        for (int il = 0; il + isize - 1 < n; il++) {
    //            int const ir = il + isize - 1;

    //            for (int jl = 0; jl + jsize - 1 < m; jl++) {
    //                int const jr = jl + jsize - 1;

    //                // top
    //                dp[il + 1][ir][jl][jr] = opponent(il, ir, jl, jr) + sum(il, il, jl, jr);
    //            }
    //        }
    //    }
    //}
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1732 KiB
2Accepted0/09ms5396 KiB
3Accepted2/23ms2240 KiB
4Accepted2/23ms2456 KiB
5Accepted1/13ms2600 KiB
6Accepted1/13ms3068 KiB
7Accepted1/14ms6004 KiB
8Accepted2/24ms4864 KiB
9Accepted3/33ms3792 KiB
10Accepted3/34ms4240 KiB
11Accepted3/36ms5872 KiB
12Accepted3/36ms6088 KiB
13Accepted4/49ms6864 KiB
14Accepted4/49ms6860 KiB
15Accepted4/412ms7128 KiB
16Accepted5/512ms7376 KiB
17Accepted5/510ms7340 KiB
18Accepted5/512ms7592 KiB
19Accepted1/110ms7544 KiB
20Accepted1/110ms7548 KiB