Submission #229765

#TimeUsernameProblemLanguageResultExecution timeMemory
229765NONAMEMaja (COCI18_maja)C++17
110 / 110
274 ms760 KiB
#include <bits/stdc++.h> #define sz(x) int(x.size()) #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #define N 100500 #define oo ll(1e16) #define ft first #define sd second #define pb push_back #define ppb pop_back #define el '\n' #define elf endl #define base ll(1e9 + 7) using namespace std; typedef long long ll; typedef long double ld; int n, m, mx, k, a, b; ll f[2][101][101], c[101][101], res; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // in("input.txt"); cin >> n >> m >> a >> b >> k; a--; b--; k >>= 1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> c[i][j]; mx = min(k, n * m); for (int t = 0; t <= 1; t++) for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) f[t][i][j] = -1; f[1][a][b] = 0; for (int t = 0; t < mx; t++) { int cur = t & 1; int lst = cur ^ 1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) f[cur][i][j] = -1; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (i - 1 >= 0 && f[lst][i - 1][j] != -1) f[cur][i][j] = max(f[cur][i][j], f[lst][i - 1][j] + c[i][j]); if (j - 1 >= 0 && f[lst][i][j - 1] != -1) f[cur][i][j] = max(f[cur][i][j], f[lst][i][j - 1] + c[i][j]); if (i + 1 < n && f[lst][i + 1][j] != -1) f[cur][i][j] = max(f[cur][i][j], f[lst][i + 1][j] + c[i][j]); if (j + 1 < m && f[lst][i][j + 1] != -1) f[cur][i][j] = max(f[cur][i][j], f[lst][i][j + 1] + c[i][j]); } } int cur = (mx - 1) & 1; // for (int i = 0; i < n; i++) // for (int j = 0; j < m; j++) // if (f[cur][i][j] != -1) // res = max(res, 2 * f[cur][i][j] + c[i][j]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int cnt = k - mx; if (cnt < 0) continue; ll v = c[i][j]; ll t = 0; if (i - 1 >= 0) t = max(t, c[i - 1][j]); if (j - 1 >= 0) t = max(t, c[i][j - 1]); if (i + 1 < n) t = max(t, c[i + 1][j]); if (j + 1 < m) t = max(t, c[i][j + 1]); v += t; res = max(res, 2 * f[cur][i][j] + v * cnt - c[i][j]); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...