제출 #113652

#제출 시각아이디문제언어결과실행 시간메모리
113652popovicirobertThe Kingdom of JOIOI (JOI17_joioi)C++14
15 / 100
14 ms2304 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; const int INF = 1e9; const int MAXN = 2000; int mat[MAXN + 1][MAXN + 1], aux[MAXN + 1][MAXN + 1]; int n, m, mn, mx; inline void rot() { int i, j; for(i = 1; i <= m; i++) { for(j = 1; j <= n; j++) { aux[i][j] = mat[n - j + 1][i]; } } swap(n, m); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { mat[i][j] = aux[i][j]; } } } inline bool solve(int dif) { int l = INF, r = -INF; int last = m; for(int j = 1; j <= m; j++) { int i = 1; while(i <= min(n, last) && mat[i][j] <= mn + dif) { i++; } last = min(last, i - 1); while(i <= n) { l = min(l, mat[i][j]); r = max(r, mat[i][j]); i++; } } if(r - l <= dif) { return 1; } last = 1; l = INF, r = -INF; for(int j = 1; j <= m; j++) { int i = n; while(i >= max(1, last) && mat[i][j] <= mn + dif) { i--; } last = max(last, i + 1); while(i >= 1) { l = min(l, mat[i][j]); r = max(r, mat[i][j]); if(r - l > dif) { return 0; } i--; } } return r - l <= dif; } inline bool check(int dif) { bool ans = 0; for(int i = 0; i < 4 && ans == 0; i++) { if(i % 2 == 0) { ans |= solve(dif); } rot(); } return ans; } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, j; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; mx = -INF, mn = INF; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { cin >> mat[i][j]; mn = min(mn, mat[i][j]); mx = max(mx, mat[i][j]); } } int res = -1; for(int step = 1 << 29; step; step >>= 1) { if(res + step <= mx - mn && check(res + step) == 0) { res += step; } } cout << res + 1; //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...