Submission #536162

#TimeUsernameProblemLanguageResultExecution timeMemory
536162cig32Maxcomp (info1cup18_maxcomp)C++17
60 / 100
1066 ms26444 KiB
#include "bits/stdc++.h" using namespace std; const int MAXN = 2e5 + 10; const int MOD = 1e9 + 7; #define int long long mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } void solve(int tc) { int n, m; cin >> n >> m; int a[n+1][m+1]; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin >> a[i][j]; } } int ans = -1e9; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { int mi = a[i][j]; bool can[n*m + 1]; for(int k=1; k<=n; k++) { for(int l=1; l<=m; l++) { can[(k-1)*m + l] = (a[k][l] >= mi ? 1 : 0); } } bool vis[n*m + 1]; int dist[n*m + 1]; for(int k=1; k<=n*m; k++) vis[k] = 0, dist[k] = 1e18; dist[(i-1)*m + j] = 1; queue<int> q; q.push((i-1)*m + j); while(q.size()) { int f=q.front(); q.pop(); if(!vis[f]) { vis[f] = 1; vector<pair<int, int> > dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for(pair<int, int> x: dirs) { int old_r = (f-1) / m + 1, old_c = (f-1) % m + 1; old_r += x.first, old_c += x.second; if(min(old_r, old_c) >= 1 && old_r <= n && old_c <= m) { int id = (old_r-1) * m + old_c; if(!vis[id] && can[id] && dist[id] > dist[f] + 1) { dist[id] = dist[f] + 1; q.push(id); } } } } } for(int k=1; k<=n; k++) { for(int l=1; l<=m; l++) { if(can[(k-1)*m + l] && dist[(k-1)*m + l] != 1e18) { ans = max(ans, a[k][l] - mi - dist[(k-1)*m + l]); } } } } } cout << ans << "\n"; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...