Submission #750487

#TimeUsernameProblemLanguageResultExecution timeMemory
750487TrunktyMaja (COCI18_maja)C++14
55 / 110
5 ms1876 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll int n,m,a,b,k,ans; int arr[105][105]; int best[105][105]; vector<vector<int>> bfs[205]; bool check[105][105]; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> a >> b >> k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >> arr[i][j]; } } bfs[1].push_back({a,b}); for(int i=1;i<=200;i++){ for(vector<int> j:bfs[i]){ int x = j[0], y = j[1]; if(check[x][y]){ continue; } check[x][y] = true; if(x>=1 and !check[x-1][y]){ best[x-1][y] = max(best[x-1][y],best[x][y]+arr[x-1][y]); bfs[i+1].push_back({x-1,y}); } if(x<=n and !check[x+1][y]){ best[x+1][y] = max(best[x+1][y],best[x][y]+arr[x+1][y]); bfs[i+1].push_back({x+1,y}); } if(y>=1 and !check[x][y-1]){ best[x][y-1] = max(best[x][y-1],best[x][y]+arr[x][y-1]); bfs[i+1].push_back({x,y-1}); } if(y<=m and !check[x][y+1]){ best[x][y+1] = max(best[x][y+1],best[x][y]+arr[x][y+1]); bfs[i+1].push_back({x,y+1}); } } } k /= 2LL; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(abs(i-a)+abs(j-b)<=k){ ans = max(ans,best[i][j]*2LL-arr[i][j]+(k-abs(i-a)-abs(j-b))*(arr[i][j]+max(max(arr[i+1][j],arr[i-1][j]),max(arr[i][j+1],arr[i][j-1])))); } } } cout << ans << "\n"; 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...