Submission #670751

#TimeUsernameProblemLanguageResultExecution timeMemory
670751MohammadAghilThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
2710 ms53188 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); #ifndef ONLINE_JUDGE #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #else #define er(args ...) 0 #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 2e3 + 5, lg = 22, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;} int n, m; int a[maxn][maxn], b[maxn][maxn]; pair<int, pp> mx; ll slv(){ // er(mx.ff, mx.ss.ff, mx.ss.ss); auto get = [&](int x){ x = mx.ff - x - 1; int ptr = n; int mxx = 0, mnn = inf; rep(j,0,m){ rep(i,0,ptr) if(a[i][j] <= x){ ptr = i; break; } // er(j, ptr); if(j == mx.ss.ss){ if(ptr <= mx.ss.ff) return int(inf); } rep(i,ptr,n){ mxx = max(mxx, a[i][j]); mnn = min(mnn, a[i][j]); } } return mxx - mnn; }; int lx = -1, rx = mx.ff; while(lx + 1 < rx){ int mid = (lx + rx)>>1; // er(mid, get(mid)); if(mid < get(mid)) lx = mid; else rx = mid; } // er(lx); return min(lx+1, get(lx)); } int main(){ IOS(); cin >> n >> m; rep(i,0,n){ rep(j,0,m) { cin >> a[i][j]; mx = max(mx, {a[i][j], {i, j}}); } } ll ans = slv(); // rep(i,0,n){ // rep(j,0,m){ // b[i][j] = a[n-1-i][m-1-j]; // } // } // rep(i,0,n){ // rep(j,0,m){ // a[i][j] = b[i][j]; // } // } // mx.ss.ff = n-1-mx.ss.ff, mx.ss.ss = m-1-mx.ss.ss; // ans = min(ans, slv()); rep(i,0,n){ rep(j,0,m){ b[i][j] = a[i][m-1-j]; } } rep(i,0,n){ rep(j,0,m){ a[i][j] = b[i][j]; } } mx.ss.ss = m-1-mx.ss.ss; ans = min(ans, slv()); rep(i,0,n){ rep(j,0,m){ b[i][j] = a[n-1-i][j]; } } rep(i,0,n){ rep(j,0,m){ a[i][j] = b[i][j]; } } mx.ss.ff = n-1-mx.ss.ff; ans = min(ans, slv()); rep(i,0,n){ rep(j,0,m){ b[i][j] = a[i][m-1-j]; } } rep(i,0,n){ rep(j,0,m){ a[i][j] = b[i][j]; } } mx.ss.ss = m-1-mx.ss.ss; ans = min(ans, slv()); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...