Submission #118703

#TimeUsernameProblemLanguageResultExecution timeMemory
118703sofhiasouzaMaja (COCI18_maja)C++14
0 / 110
2065 ms65536 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 110, maxs = 1e4+10; int n, m, a, b, mat[maxn][maxn], k; struct pt { ll f; int sf, ss; bool operator > (const pt &k) const{ if(f != k.f) return f > k.f; else if(sf != k.sf) return sf > k.sf; else return ss >= k.ss; } }dp[maxn][maxn][2]; pt solve() { int mod = 0; for(int t = 1 ; t <= min(k, 10000) ; t++) { mod ^= 1; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { if(i == 3 and j == 3) { cout << dp[i-1][j][mod^1].f << ' ' << dp[i][j+1][mod^1].f << ' ' << dp[i][j-1][mod^1].f << ' ' << dp[i+1][j][mod^1].f << endl; } if(dp[i-1][j][mod^1] > dp[i+1][j][mod^1] and dp[i-1][j][mod^1] > dp[i][j-1][mod^1] and dp[i-1][j][mod^1] > dp[i][j+1][mod^1]) { dp[i][j][mod] = dp[i-1][j][mod^1]; if(mat[i][j] > dp[i-1][j][mod^1].sf) { dp[i][j][mod].ss = dp[i-1][j][mod^1].sf; dp[i][j][mod].sf = mat[i][j]; } else if(mat[i][j] > dp[i-1][j][mod^1].ss) dp[i][j][mod].ss = mat[i][j]; } else if(dp[i+1][j][mod^1] > dp[i-1][j][mod^1] and dp[i+1][j][mod^1] > dp[i][j-1][mod^1] and dp[i+1][j][mod^1] > dp[i][j+1][mod^1]) { dp[i][j][mod] = dp[i+1][j][mod^1]; if(mat[i][j] > dp[i+1][j][mod^1].sf) { dp[i][j][mod].ss = dp[i+1][j][mod^1].sf; dp[i][j][mod].sf = mat[i][j]; } else if(mat[i][j] > dp[i+1][j][mod^1].ss) dp[i][j][mod].ss = mat[i][j]; } else if(dp[i][j-1][mod^1] > dp[i-1][j][mod^1] and dp[i][j-1][mod^1] > dp[i+1][j][mod^1] and dp[i][j-1][mod^1] > dp[i][j+1][mod^1]) { dp[i][j][mod] = dp[i][j-1][mod^1]; if(mat[i][j] > dp[i][j-1][mod^1].sf) { dp[i][j][mod].ss = dp[i][j-1][mod^1].sf; dp[i][j][mod].sf = mat[i][j]; } else if(mat[i][j] > dp[i][j-1][mod^1].ss) dp[i][j][mod].ss = mat[i][j]; } else { dp[i][j][mod] = dp[i][j+1][mod^1]; if(mat[i][j] > dp[i][j+1][mod^1].sf) { dp[i][j][mod].ss = dp[i][j+1][mod^1].sf; dp[i][j][mod].sf = mat[i][j]; } else if(mat[i][j] > dp[i][j+1][mod^1].ss) dp[i][j][mod].ss = mat[i][j]; } if(dp[i][j][mod].f != -1) dp[i][j][mod].f += mat[i][j]; if(dp[i][j][mod].sf < dp[i][j][mod].ss) swap(dp[i][j][mod].sf, dp[i][j][mod].ss); } } cout << endl << t << endl; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { cout << dp[i][j][mod].f << ' '; } cout << endl; } //cout << endl; } return dp[a][b][mod]; } int main() { cin >> n >> m >> a >> b >> k; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { cin >> mat[i][j]; } } memset(dp, -1, sizeof dp); dp[a][b][0].f = 0; pt resp = solve(); if(k < 1e4) cout << resp.f << endl; else cout << resp.f + (resp.sf+resp.ss)*k/2 << endl; }
#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...