Submission #1051688

#TimeUsernameProblemLanguageResultExecution timeMemory
1051688alex_2008The Kingdom of JOIOI (JOI17_joioi)C++14
15 / 100
5 ms6744 KiB
#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <set> using namespace std; typedef long long ll; const int N = 2024; int a[N][N]; bool used[N][N]; int n, m; int mn; bool f(int d) { int mn = 1e9 + 10, mx = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!used[i][j]) { mx = max(mx, a[i][j]); mn = min(mn, a[i][j]); } } } if ((mx - mn) <= d) return true; return false; } bool ch(int d) { int last_h = n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = false; } } for (int j = m; j >= 1; j--) { for (int i = n; i >= n - last_h + 1; i--) { if (a[i][j] > (mn + d)) { last_h = n - i + 1; break; } used[i][j] = true; } } if (f(d)) return true; last_h = n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = false; } } for (int j = 1; j <= m; j++) { for (int i = n; i >= n - last_h + 1; i--) { if (a[i][j] > (mn + d)) { last_h = n - i + 1; break; } used[i][j] = true; } } if (f(d)) return true; last_h = n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = false; } } for (int j = 1; j <= m; j++) { for (int i = 1; i <= last_h; i++) { if (a[i][j] > (mn + d)) { last_h = i; break; } used[i][j] = true; } } if (f(d)) return true; last_h = n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = false; } } for (int j = m; j >= 1; j--) { for (int i = 1; i <= last_h; i++) { if (a[i][j] > (mn + d)) { last_h = i; break; } used[i][j] = true; } } if (f(d)) return true; return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); mn = 1000000010; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; mn = min(mn, a[i][j]); } } int l = 0, r = 1000000010, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (ch(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...