Submission #864325

#TimeUsernameProblemLanguageResultExecution timeMemory
864325Dec0DeddThe Kingdom of JOIOI (JOI17_joioi)C++14
60 / 100
4070 ms86028 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #define sh short #define pp pair<sh, sh> const int N = 2e3+110; const int INF = 1e9; int a[N][N], cnt[N], h, w; vector<int> v; void fs(int &number) { register int c; number = 0; c = getchar(); for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48; } bool cmp(sh x, sh y) { return a[cnt[x]+1][x] > a[cnt[y]+1][y]; } deque<pp> tmp; int solve() { memset(cnt, 0, sizeof(cnt)); int res=INF, lis=INF, uis=-1; deque<pp> q=tmp; priority_queue<sh, vector<sh>, function<bool(sh, sh)>> pq(cmp); pq.push(w); for (int k=0; k<(int)v.size(); ++k) { while (!pq.empty()) { if (a[cnt[pq.top()]+1][pq.top()] <= v[k]) { sh x=pq.top(); pq.pop(); int val=a[cnt[x]+1][x]; lis=min(lis, val), uis=max(uis, val); ++cnt[x]; if (cnt[x] == h) continue; if (x == w || cnt[x+1] >= cnt[x]+1) pq.push(x); if (x == 1) continue; if (cnt[x] == cnt[x-1]+1) pq.push(x-1); } else break; } while (!q.empty()) { int i=q.front().first, j=q.front().second; if (i <= cnt[j]) q.pop_front(); else break; } while (!q.empty()) { int i=q.back().first, j=q.back().second; if (i <= cnt[j]) q.pop_back(); else break; } int lf; if (q.empty()) lf=INF; else { int x=a[q.back().first][q.back().second]; int y=a[q.front().first][q.front().second]; lf=x-y; } res=min(res, max(lf, uis-lis)); } return res; } void hor() { for (int i=1; i<h/2+1; ++i) { for (int j=1; j<=w; ++j) swap(a[i][j], a[h-i+1][j]); } } void ver() { for (int i=1; i<=h; ++i) { for (int j=1; j<w/2+1; ++j) swap(a[i][j], a[i][w-j+1]); } } bool cmpx(pp x, pp y) { return a[x.first][x.second] < a[y.first][y.second]; } void filltmp() { sort(tmp.begin(), tmp.end(), cmpx); } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); fs(h), fs(w); for (int i=1; i<=h; ++i) { for (int j=1; j<=w; ++j) { fs(a[i][j]); v.push_back(a[i][j]); } } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i=1; i<=h; ++i) { for (int j=1; j<=w; ++j) tmp.push_back({i, j}); } filltmp(); int ans=solve(); hor(); filltmp(); ans=min(ans, solve()); hor(); ver(); filltmp(); ans=min(ans, solve()); hor(); filltmp(); ans=min(ans, solve()); printf("%d\n", ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...