제출 #87903

#제출 시각아이디문제언어결과실행 시간메모리
87903tieunhiThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
2285 ms53992 KiB
#include <bits/stdc++.h> #define pii pair<ll, ll> #define mp make_pair #define F first #define S second #define PB push_back #define FOR(i, u, v) for (int i = u; i <= v; i++) #define FORD(i, v, u) for (int i = v; i >= u; i--) #define ll long long #define N 2003 #define LN 19 #define maxc 1000000007 using namespace std; int n, m, a[N][N], amin, amax, pos[N]; bool b[N][N]; void revRow() { FOR(i, 1, n) FOR(j, 1, m/2) swap(a[i][j], a[i][m-j+1]); } void revCol() { FOR(j, 1, m) FOR(i, 1, n/2) swap(a[i][j], a[n-i+1][j]); } bool ok(int diff) { FOR(i, 1, n) FOR(j, 1, m) b[i][j] = (a[i][j] >= (amax - diff)); pos[0] = m; FOR(i, 1, n) { pos[i] = pos[i-1]; FOR(j, 1, pos[i-1]) if (b[i][j] == 0) {pos[i] = j-1; break;} } int mx = 0, mn = maxc; if (pos[n] == m) return 1; FOR(i, 1, n) FOR(j, pos[i]+1, m) { mx = max(mx, a[i][j]); mn = min(mn, a[i][j]); } if (abs(mx - mn) <= diff) return 1; return 0; } bool check(int diff) { if (ok(diff)) return 1; revRow(); if (ok(diff)) return 1; revCol(); if (ok(diff)) return 1; revRow(); if (ok(diff)) return 1; return 0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> n >> m; amin = maxc, amax = 0; FOR(i, 1, n) FOR(j, 1, m) { cin >> a[i][j]; amax = max(amax, a[i][j]); amin = min(amin, a[i][j]); } int l = 0, r = amax - amin + 1; while (r - l > 1) { int mid = (r + l)/2; if (check(mid)) r = mid; else l = mid; } cout <<r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...