# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
229023 |
2020-05-03T09:20:54 Z |
VEGAnn |
Maja (COCI18_maja) |
C++14 |
|
598 ms |
16424 KB |
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int CNST = 2;
const ll N = 110;
const ll PW = 22;
int step[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll c[N][N], a, b, n, m, k;
ll ans[2 * N][N][N];
void MAX(ll &x, ll y){
x = max(x, y);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> a >> b >> k;
a--; b--;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++)
cin >> c[i][j];
ans[0][a][b] = 1;
int cnst = (n + m);
for (ll ite = 1; ite <= cnst; ite++){
// for (ll ite = 1; ite <= CNST; ite++){
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++){
if (ans[ite - 1][i][j] == 0) continue;
if (i > 0) MAX(ans[ite][i - 1][j], ans[ite - 1][i][j] + c[i - 1][j]);
if (j > 0) MAX(ans[ite][i][j - 1], ans[ite - 1][i][j] + c[i][j - 1]);
if (j + 1 < m) MAX(ans[ite][i][j + 1], ans[ite - 1][i][j] + c[i][j + 1]);
if (i + 1 < n) MAX(ans[ite][i + 1][j], ans[ite - 1][i][j] + c[i + 1][j]);
}
}
if (k <= cnst)
cout << ans[k][a][b] - 1 << '\n';
else {
ll res = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
ll mx = 0;
if (i > 0) MAX(mx, c[i - 1][j]);
if (j > 0) MAX(mx, c[i][j - 1]);
if (j + 1 < m) MAX(mx, c[i][j + 1]);
if (i + 1 < n) MAX(mx, c[i + 1][j]);
mx += c[i][j];
for (ll st = 0; st <= cnst; st++)
for (ll ed = st; ed <= cnst; ed += 2){
// for (ll st = 0; st <= CNST; st++){
if (st + ed > k) break;
if (ans[st][i][j] == 0) continue;
if (ans[ed][i][j] > 0) {
ll cur = ans[st][i][j] - 1;
ll scr = ans[ed][i][j] - 1;
res = max(res, cur + scr + mx * (k - st - ed) / 2 - c[i][j]);
}
if (ed > 0){
ll cur = ans[st][i][j] - 1;
for (int ite = 0; ite < 4; ite++) {
int cx = i + step[ite][0], cy = j + step[ite][1];
if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
ll scr = ans[ed - 1][cx][cy] - 1;
ll iter = (k - st - ed) / 2;
if (iter == 0) continue;
iter--;
res = max(res, cur + scr + iter * mx);
}
}
}
}
cout << res;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
3072 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
3 |
Incorrect |
598 ms |
16424 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1152 KB |
Output is correct |
2 |
Correct |
152 ms |
8576 KB |
Output is correct |
3 |
Incorrect |
411 ms |
14336 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
9856 KB |
Output is correct |
2 |
Correct |
212 ms |
11128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
2816 KB |
Output is correct |
2 |
Correct |
31 ms |
5992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1408 KB |
Output is correct |
2 |
Correct |
7 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
5376 KB |
Output is correct |
2 |
Correct |
5 ms |
896 KB |
Output is correct |