Submission #332873

#TimeUsernameProblemLanguageResultExecution timeMemory
332873limabeansThe Kingdom of JOIOI (JOI17_joioi)C++17
15 / 100
4077 ms512 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++) { a.push_back(g[i][j]); mn = min(mn, g[i][j]); mx = max(mx, g[i][j]); } } sort(a.begin(),a.end()); ll res = inf; for (ll x: a) { for (ll y: a) { if (x<y) { if (test(y-x)) { res = min(res, y-x); } } } } return res; } 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...