Submission #1181386

#TimeUsernameProblemLanguageResultExecution timeMemory
1181386nekolieThe Kingdom of JOIOI (JOI17_joioi)C++20
100 / 100
514 ms16132 KiB
#include <bits/stdc++.h> using namespace std; int n, m, h[2001][2001], mini = 1000000000; bool czy(int x) { bool odp = false; int dp[n+2][4], res[4][2]; dp[0][0] = dp[n+1][2] = m, dp[0][1] = dp[n+1][3] = 1; res[0][0] = res[1][0] = res[2][0] = res[3][0] = -1000000000; res[0][1] = res[1][1] = res[2][1] = res[3][1] = 1000000000; for (int i = 1; i <= n; i++) { dp[i][0] = 0, dp[i][1] = m+1; for (int j = 1; j <= dp[i-1][0]; j++) { if (h[i][j] <= mini+x) dp[i][0]++; else break; } for (int j = m; j > dp[i][0]; j--) res[0][0] = max(res[0][0],h[i][j]), res[0][1] = min(res[0][1],h[i][j]); for (int j = m; j >= dp[i-1][1]; j--) { if (h[i][j] <= mini+x) dp[i][1]--; else break; } for (int j = 1; j < dp[i][1]; j++) res[1][0] = max(res[1][0],h[i][j]), res[1][1] = min(res[1][1],h[i][j]); } for (int i = n; i >= 1; i--) { dp[i][2] = 0, dp[i][3] = m+1; for (int j = 1; j <= dp[i+1][2]; j++) { if (h[i][j] <= mini+x) dp[i][2]++; else break; } for (int j = m; j > dp[i][2]; j--) res[2][0] = max(res[2][0],h[i][j]), res[2][1] = min(res[2][1],h[i][j]); for (int j = m; j >= dp[i+1][3]; j--) { if (h[i][j] <= mini+x) dp[i][3]--; else break; } for (int j = 1; j < dp[i][3]; j++) res[3][0] = max(res[3][0],h[i][j]), res[3][1] = min(res[3][1],h[i][j]); } return (min({res[0][0]-res[0][1],res[1][0]-res[1][1],res[2][0]-res[2][1],res[3][0]-res[3][1]}) <= x); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> h[i][j], mini = min(mini,h[i][j]); int l = 0, r = 1000000000; while (l < r) { int s = (l+r)/2; if (czy(s)) r = s; else l = s+1; } cout << l << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...