7331 2024. 01. 07 17:24:22 Error42 Táblatörés cpp17 Elfogadva 50/50 12ms 7592 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);
    //            }
    //        }
    //    }
    //}
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1732 KiB
2 Elfogadva 0/0 9ms 5396 KiB
3 Elfogadva 2/2 3ms 2240 KiB
4 Elfogadva 2/2 3ms 2456 KiB
5 Elfogadva 1/1 3ms 2600 KiB
6 Elfogadva 1/1 3ms 3068 KiB
7 Elfogadva 1/1 4ms 6004 KiB
8 Elfogadva 2/2 4ms 4864 KiB
9 Elfogadva 3/3 3ms 3792 KiB
10 Elfogadva 3/3 4ms 4240 KiB
11 Elfogadva 3/3 6ms 5872 KiB
12 Elfogadva 3/3 6ms 6088 KiB
13 Elfogadva 4/4 9ms 6864 KiB
14 Elfogadva 4/4 9ms 6860 KiB
15 Elfogadva 4/4 12ms 7128 KiB
16 Elfogadva 5/5 12ms 7376 KiB
17 Elfogadva 5/5 10ms 7340 KiB
18 Elfogadva 5/5 12ms 7592 KiB
19 Elfogadva 1/1 10ms 7544 KiB
20 Elfogadva 1/1 10ms 7548 KiB