#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
signed main()
{
int n,m,a,b,K,i,j,k,ii;
cin>>n>>m>>a>>b>>K;
int L = 5000;
int dx[4] = {1,-1,0,0},ans=0;
int dy[4] = {0,0,1,-1};
int dp[n+3][m+3][2],anu[n+3][m+3],cnt=0;
memset(anu,0,sizeof(anu));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) cin>>anu[i][j];
}
for(i=0;i<=n+1;i++){
for(j=0;j<=m+1;j++){
dp[i][j][0] = dp[i][j][1] = -1e18;
}
}
dp[a][b][0] = 0;
for(k=1;k<=L;k++){
if(2*k > K) break;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(cnt%2 == 0){
int val = 0;
for(ii=0;ii<4;ii++){
val = max(val,anu[i+dx[ii]][j+dy[ii]]);
dp[i][j][1] = max(dp[i][j][k],dp[i+dx[ii]][j+dy[ii]][0]+anu[i][j]);
}
ans = max(ans,dp[i][j][1]*2-anu[i][j]+((K-2*k)/2)*(val+anu[i][j]));
}
else{
int val = 0;
for(ii=0;ii<4;ii++){
val = max(val,anu[i+dx[ii]][j+dy[ii]]);
dp[i][j][0] = max(dp[i][j][k],dp[i+dx[ii]][j+dy[ii]][1]+anu[i][j]);
}
ans = max(ans,dp[i][j][0]*2-anu[i][j]+((K-2*k)/2)*(val+anu[i][j]));
}
}
}
cnt++;
}
cout<<ans;
return 0;
}
# | 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... |