Submission #670479

#TimeUsernameProblemLanguageResultExecution timeMemory
670479radalThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef pair<int,int> pll; constexpr int N = 2e3+10,mod = 1e9+7,maxm = 210; constexpr ll inf = 1e9+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; // if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k >>= 1; } return z; } int h,w,l[N]; int a[N][N],b[N][N]; int ans,sz,mi; bool on[N][N]; multiset<int> st; vector<pll> ve; bool cmp(pll q,pll p){ return (a[p.X][p.Y] > a[q.X][q.Y]); } void rlx(int x){ if (l[x] == l[x+1] || !on[x][l[x]+1]) return; while (l[x] < l[x+1] && on[x][l[x]+1]){ l[x]++; st.erase(st.find(a[x][l[x]])); } if (x) rlx(x-1); } void rst(){ rep(i,1,h+1){ rep(j,1,l[i]+1) st.insert(a[i][j]); } rep(i,1,h+1){ l[i] = 0; rep(j,1,w+1){ a[i][j] = b[i][j]; on[i][j] = 0; } } } void calc(){ rep(i,0,sz-1){ int x = ve[i].X,y = ve[i].Y; if (a[x][y]-mi >= ans) break; on[x][y] = 1; rlx(x); if ((int)st.size() == sz) continue; ans = min(ans,max(a[x][y]-mi,(*st.rbegin())-(*st.begin()))); } } int main(){ ios :: sync_with_stdio(0); cin.tie(0); cin >> h >> w; rep(i,1,h+1){ rep(j,1,w+1){ cin >> a[i][j]; b[i][j] = a[i][j]; st.insert(a[i][j]); ve.pb({i,j}); } } l[h+1] = w; ans = (*st.rbegin())-(*st.begin()); sort(all(ve),cmp); int c = ve[0].X,d = ve[0].Y,e = ve.back().X,f = ve.back().Y; sz = h*w; mi = a[c][d]; if ((c <= e && d < f) || c > e){ calc(); rst(); } rep(i,1,h+1){ if (h-i+1 <= i) break; rep(j,1,w+1) swap(a[i][j],a[h-i+1][j]); } rep(i,0,sz){ ve[i].X = h-ve[i].X+1; } if ((c >= e && d < f) || c < e){ calc(); rst(); } rep(j,1,w+1){ if (w-j+1 <= j) break; rep(i,1,h+1) swap(a[i][j],a[i][w-j+1]); } rep(i,0,sz){ ve[i].Y = w-ve[i].Y+1; ve[i].X = h-ve[i].X+1; } if ((c <= e && d > f) || c > e){ calc(); rst(); } rep(i,1,h+1){ if (h-i+1 <= i) break; rep(j,1,w+1) swap(a[i][j],a[h-i+1][j]); } rep(j,1,w+1){ if (w-j+1 <= j) break; rep(i,1,h+1) swap(a[i][j],a[i][w-j+1]); } rep(i,0,sz){ ve[i].X = h-ve[i].X+1; } if ((c >= e && d > f) || c < e) calc(); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...