Submission #1256116

#TimeUsernameProblemLanguageResultExecution timeMemory
1256116coderpemulaMaja (COCI18_maja)C++20
110 / 110
294 ms664 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back using namespace std; int dp[103][103][2],anu[103][103]; 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 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][1],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][0],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...