Submission #339173

#TimeUsernameProblemLanguageResultExecution timeMemory
339173Atill83The Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
974 ms70840 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 2e3+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll h, w; int mx = 0, mn = mod; int g[MAXN][MAXN], ot[MAXN][MAXN]; inline void turn(){ for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) ot[j][h - 1 - i] = g[i][j]; swap(h, w); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) g[i][j] = ot[i][j]; } inline bool check(int del){ int sn = 0; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(g[i][j] < mx - del) sn = max(sn, j + 1); } for(int j = 0; j < sn; j++){ if(g[i][j] > mn + del) return 0; } } return 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>h>>w; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){ cin>>g[i][j]; mx = max(mx, g[i][j]); mn = min(mn, g[i][j]); } int ans = mod; int cn = 0; do{ int l = 0, r = (int) 1e9; while(l < r){ int m = (l + r) / 2; if(check(m)) r = m; else l = m + 1; } ans = min(ans, l); turn(); } while(++cn < 4); cout<<ans<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...