This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |