173202025-06-24 09:59:41szilRusco in Bolognacpp17Elfogadva 100/100232ms66276 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 201;
const ll INF = -1e16;

ll dp[2*MAXN][MAXN][MAXN];
int p1[MAXN][MAXN];
pair<int, int> p2[2*MAXN][MAXN];

pair<int, int> DIR[2] = {{-1, 0}, {0, -1}};

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<ll>> v(n+m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll x; cin >> x;
            p1[i][j] = v[i+j].size();
            p2[i+j][v[i+j].size()] = {i, j};
            v[i+j].emplace_back(x);
        }
    }
    // for (int i = 0; i < n+m; i++) {
    //     for (int j : v[i]) cerr << j << " ";
    //     cerr << endl;
    // }
    auto is_ok = [&](int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    };
    dp[0][0][0] = v[0][0];
    for (int i = 1; i < n+m; i++) {
        int len = v[i].size();
        for (int l = 0; l < len; l++) {
            for (int r = 0; r < len; r++) {
                ll val = (l == r) ? (v[i][l]) : (v[i][l] + v[i][r]);
                dp[i][l][r] = INF;

                auto [x1, y1] = p2[i][l];
                auto [x2, y2] = p2[i][r];

                for (auto [dx1, dy1] : DIR) {
                    for (auto [dx2, dy2] : DIR) {
                        int nx1 = x1 + dx1;
                        int nx2 = x2 + dx2;
                        int ny1 = y1 + dy1;
                        int ny2 = y2 + dy2;
                        if (!is_ok(nx1, ny1) || !is_ok(nx2, ny2)) continue;
                        dp[i][l][r] = max(dp[i][l][r], dp[i-1][p1[nx1][ny1]][p1[nx2][ny2]] + val);
                    }
                }
            }
        }
    }
    // for (int i = 0; i < n+m; i++) {
    //     cerr << i << ":\n";
    //     int len = v[i].size();
    //     for (int x = 0; x < len; x++) {
    //         for (int y = 0; y < len; y++) {
    //             cerr << dp[i][x][y] << " ";
    //         }
    //         cerr << endl;
    //     }
    //     cerr << endl;
    // }
    cout << dp[n+m-2][0][0] << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
subtask24/4
2Elfogadva1ms316 KiB
3Elfogadva2ms1844 KiB
subtask330/30
4Elfogadva1ms316 KiB
5Elfogadva1ms820 KiB
6Elfogadva2ms2100 KiB
7Elfogadva2ms2100 KiB
8Elfogadva3ms2100 KiB
subtask419/19
9Elfogadva1ms316 KiB
10Elfogadva1ms564 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms1012 KiB
13Elfogadva4ms3380 KiB
14Elfogadva4ms2616 KiB
15Elfogadva3ms2612 KiB
16Elfogadva4ms3396 KiB
17Elfogadva4ms3204 KiB
subtask547/47
18Elfogadva1ms512 KiB
19Elfogadva2ms1844 KiB
20Elfogadva1ms316 KiB
21Elfogadva3ms2100 KiB
22Elfogadva222ms66276 KiB
23Elfogadva232ms66224 KiB
24Elfogadva146ms50092 KiB
25Elfogadva155ms49968 KiB
26Elfogadva219ms66100 KiB
27Elfogadva231ms66100 KiB
28Elfogadva218ms66100 KiB
29Elfogadva230ms66100 KiB