| 17320 | 2025-06-24 09:59:41 | szil | Rusco in Bologna | cpp17 | Elfogadva 100/100 | 232ms | 66276 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| subtask2 | 4/4 | ||||||
| 2 | Elfogadva | 1ms | 316 KiB | ||||
| 3 | Elfogadva | 2ms | 1844 KiB | ||||
| subtask3 | 30/30 | ||||||
| 4 | Elfogadva | 1ms | 316 KiB | ||||
| 5 | Elfogadva | 1ms | 820 KiB | ||||
| 6 | Elfogadva | 2ms | 2100 KiB | ||||
| 7 | Elfogadva | 2ms | 2100 KiB | ||||
| 8 | Elfogadva | 3ms | 2100 KiB | ||||
| subtask4 | 19/19 | ||||||
| 9 | Elfogadva | 1ms | 316 KiB | ||||
| 10 | Elfogadva | 1ms | 564 KiB | ||||
| 11 | Elfogadva | 1ms | 316 KiB | ||||
| 12 | Elfogadva | 1ms | 1012 KiB | ||||
| 13 | Elfogadva | 4ms | 3380 KiB | ||||
| 14 | Elfogadva | 4ms | 2616 KiB | ||||
| 15 | Elfogadva | 3ms | 2612 KiB | ||||
| 16 | Elfogadva | 4ms | 3396 KiB | ||||
| 17 | Elfogadva | 4ms | 3204 KiB | ||||
| subtask5 | 47/47 | ||||||
| 18 | Elfogadva | 1ms | 512 KiB | ||||
| 19 | Elfogadva | 2ms | 1844 KiB | ||||
| 20 | Elfogadva | 1ms | 316 KiB | ||||
| 21 | Elfogadva | 3ms | 2100 KiB | ||||
| 22 | Elfogadva | 222ms | 66276 KiB | ||||
| 23 | Elfogadva | 232ms | 66224 KiB | ||||
| 24 | Elfogadva | 146ms | 50092 KiB | ||||
| 25 | Elfogadva | 155ms | 49968 KiB | ||||
| 26 | Elfogadva | 219ms | 66100 KiB | ||||
| 27 | Elfogadva | 231ms | 66100 KiB | ||||
| 28 | Elfogadva | 218ms | 66100 KiB | ||||
| 29 | Elfogadva | 230ms | 66100 KiB | ||||