Submission #1256113

#TimeUsernameProblemLanguageResultExecution timeMemory
1256113coderpemulaMaja (COCI18_maja)C++20
0 / 110
13 ms584 KiB
#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 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...