| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1251934 | altern23 | Maja (COCI18_maja) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;
ll C[105][105];
ll dp[105][105][205];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll N, M, A, B, K; cin >> N >> M >> A >> B >> K;
K /= 2;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> C[i][j];
for(int k = 0; k <= N + M; k++) dp[i][j][k] = -INF;
}
}
dp[A][B][0] = 0;
for(int k = 1; k <= 10005; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
if(i > 1) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + C[i][j]);
if(i < N) dp[i][j][k] = max(dp[i][j][k], dp[i + 1][j][k - 1] + C[i][j]);
if(j > 1) dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + C[i][j]);
if(j < M) dp[i][j][k] = max(dp[i][j][k], dp[i][j + 1][k - 1] + C[i][j]);
}
}
}
ll ans = 0;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
for(int k = 1; k <= min(K, 10005); k++){
ll res = K - k;
if(i > 1) ans = max(ans, 2LL * (dp[i][j][k] + C[i][j] * (res / 2) + C[i - 1][j] * ((res + 1) / 2)) - (res % 2 ? C[i - 1][j] : C[i][j]));
if(i < N) ans = max(ans, 2LL * (dp[i][j][k] + C[i][j] * (res / 2) + C[i + 1][j] * ((res + 1) / 2)) - (res % 2 ? C[i + 1][j] : C[i][j]));
if(j > 1) ans = max(ans, 2LL * (dp[i][j][k] + C[i][j] * (res / 2) + C[i][j - 1] * ((res + 1) / 2)) - (res % 2 ? C[i][j - 1] : C[i][j]));
if(j < M) ans = max(ans, 2LL * (dp[i][j][k] + C[i][j] * (res / 2) + C[i][j + 1] * ((res + 1) / 2)) - (res % 2 ? C[i][j + 1] : C[i][j]));
}
}
}
cout << ans << "\n";
}
}