Submission #1003456

#TimeUsernameProblemLanguageResultExecution timeMemory
1003456vako_pThe Kingdom of JOIOI (JOI17_joioi)C++14
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int mxN = 2e3 + 5; ll n,m,a[mxN][mxN],p[mxN][mxN],b[mxN][mxN]; pair<ll,ll> idx; bool vis[mxN][mxN]; bool turn(ll mid){ for(int j = 1; j <= m; j++){ for(int i = n; i > 0; i--){ b[j][n - i + 1] = a[i][j]; } } idx = {idx.second, n - idx.first + 1}; swap(m, n); // cout << '\n'; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ a[i][j] = b[i][j]; // cout << a[i][j] << ' '; p[i][j] = max(p[i - 1][j], p[i][j - 1]); p[i][j] = max(p[i][j], a[i][j]); vis[i][j] = false; } // cout << '\n'; } // cout << idx.first << ' ' << idx.second << '\n'; ll x = idx.first, y = idx.second; if(p[x][y] - a[x][y] > mid) return false; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(p[i][j] - a[x][y] > mid) break; vis[i][j] = true; } } ll mx = 0, mn = 1e17; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ // cout << vis[i][j] << ' '; if(vis[i][j]) continue; mn = min(mn, a[i][j]); mx = max(mx, a[i][j]); } // cout << '\n'; } // cout << '\n'; return (mx - mn <= mid); } bool ok(ll mid){ return (turn(mid) or turn(mid) or turn(mid) or turn(mid)); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; ll mn = 1e17; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; if(mn > a[i][j]){ idx = {i, j}; mn = a[i][j]; } } } ll l = 0, r = 2e17; while(r > l + 1){ ll mid = l + (r - l) / 2; if(ok(mid)) r = mid; else l = mid; } cout << r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...