This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <string.h>
#define N 100
#define M 100
#define K 40404
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
static int aa[N][M];
static long long dp[N][M];
int n, m, k, k_, h, i, j, is, js, l;
long long ans;
scanf("%d%d%d%d%d", &n, &m, &is, &js, &k), is--, js--, k /= 2;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i][j]);
for (i = 0; i < n; i++)
memset(dp[i], -1, m * sizeof *dp[i]);
dp[is][js] = aa[is][js];
ans = 0;
k_ = min(k, k % 2 == 0 ? K : K + 1);
for (l = 1; l <= k_; l++)
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if ((i + is + j + js + l) % 2 == 0) {
long long x = -1;
for (h = 0; h < 4; h++) {
int i_ = i + di[h], j_ = j + dj[h];
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && dp[i_][j_] != -1)
x = max(x, dp[i_][j_] + aa[i][j]);
}
dp[i][j] = x;
}
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if ((i + is + j + js + k) % 2 == 0 && dp[i][j] != -1) {
int a = 0;
for (h = 0; h < 4; h++) {
int i_ = i + di[h], j_ = j + dj[h];
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m)
a = max(a, aa[i_][j_]);
}
ans = max(ans, dp[i][j] * 2 - aa[i][j] + (long long) (aa[i][j] + a) * (k - k_));
}
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
maja.c: In function 'main':
maja.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d%d%d%d%d", &n, &m, &is, &js, &k), is--, js--, k /= 2;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maja.c:23:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%d", &aa[i][j]);
| ^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |