Submission #332874

#TimeUsernameProblemLanguageResultExecution timeMemory
332874limabeansThe Kingdom of JOIOI (JOI17_joioi)C++17
60 / 100
4101 ms102420 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl using ll = long long; const ll inf = 1e18; const int maxn = 2020; int n,m; ll g[maxn][maxn]; ll tmp[maxn][maxn]; bool test(ll diff) { ll mn = inf; ll mx = -inf; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { mn = min(mn, g[i][j]); mx = max(mx, g[i][j]); } } { int sep = 0; bool ok = true; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (g[i][j]<mx-diff) { sep = max(sep,j+1); } } for (int j=0; j<m; j++) { if (g[i][j]>mn+diff) { if (j<sep) ok = false; } } } if (ok) return true; } { int sep = 0; bool ok = true; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (g[i][j]>mn+diff) { sep = max(sep,j+1); } } for (int j=0; j<m; j++) { if (g[i][j]<mx-diff) { if (j<sep) ok = false; } } } if (ok) return true; } return false; } ll solve() { ll mn = inf; ll mx = -inf; vector<ll> a; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { mn = min(mn, g[i][j]); mx = max(mx, g[i][j]); } } ll diff = mx-mn; ll hi = diff; ll lo = -1; while (hi-lo>1) { ll mid = (lo+hi)/2; if (test(mid)) { hi = mid; } else { lo = mid; } } return hi; } void flipY() { for (int i=0; i<n; i++) { for (int j=0; j<m/2; j++) { swap(g[i][j],g[i][m-j-1]); } } } void transpose() { for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { tmp[j][i]=g[i][j]; } } swap(n,m); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { g[i][j]=tmp[i][j]; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { cin>>g[i][j]; } } ll res = inf; res = min(res, solve()); flipY(); res = min(res, solve()); flipY(); transpose(); res = min(res, solve()); flipY(); res = min(res, solve()); cout<<res<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...