Submission #995269

#TimeUsernameProblemLanguageResultExecution timeMemory
995269gmroh06The Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
718 ms61308 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; using tll = tuple<ll, ll, ll, ll>; inline void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } const ll INF = 1e18; ll h, w, mn = INF, mx, ans = INF; vector<vector<ll>> v; bool chk(ll val) { for (ll i = 0, tmp = 0; i < h; i++) { for (ll j = 0; j < w; j++) if (v[i][j] + val < mx) { tmp = max(tmp, j + 1); } for (ll j = 0; j < w; j++) if (v[i][j] > mn + val and j < tmp) { return false; } } return true; } ll cal() { ll s = 0, e = mx - mn; while (s < e) { ll mid = (s + e) / 2; if (chk(mid)) { e = mid; } else { s = mid + 1; } } return s; } int main() { fastio(); cin >> h >> w; v.resize(h, vector<ll>(w)); for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++) { cin >> v[i][j]; mx = max(v[i][j], mx); mn = min(v[i][j], mn); } ans = min(ans, cal()); reverse(v.begin(), v.end()); ans = min(ans, cal()); for (auto& x : v) { reverse(x.begin(), x.end()); } ans = min(ans, cal()); reverse(v.begin(), v.end()); ans = min(ans, cal()); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...