Submission #332871

#TimeUsernameProblemLanguageResultExecution timeMemory
332871limabeansThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
9 ms492 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]; int mark[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]); } } for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { mark[i][j] = -1; } } for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (mark[i][j]==-1) { if (g[i][j]<mx-diff) { mark[i][j]=0; } else if (mn+diff<g[i][j]) { mark[i][j]=1; } } } } int right0 = m-1; for (int i=0; i<n; i++) { int r0 = 0; int l1 = m; for (int j=0; j<m; j++) { if (mark[i][j]==0) { r0=j; } else if (mark[i][j]==1) { l1=min(l1,j); } } if (r0>l1) return false; if (r0>right0) return false; right0 = min(right0, l1-1); //watch(right0); } return true; } 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...