Submission #396949

#TimeUsernameProblemLanguageResultExecution timeMemory
396949timmyfengThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
731 ms44144 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2001; int prefix[N], suffix[N], diff[N][N], a[N][N]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int maxi = INT_MIN, mini = INT_MAX; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> a[i][j]; maxi = max(maxi, a[i][j]); mini = min(mini, a[i][j]); } } fill(diff[0], diff[0] + m + 1, INT_MIN); int ans = INT_MAX; for (int k = 0; k < 2; ++k) { for (int i = 0; i < n; ++i) { reverse(a[i], a[i] + m); } for (int l = 0; l < 2; ++l) { reverse(a, a + n); for (int i = 0; i < n; ++i) { copy(a[i], a[i] + m, prefix); for (int j = 1; j < m; ++j) { prefix[j] = min(prefix[j], prefix[j - 1]); } copy(a[i], a[i] + m, suffix); for (int j = m - 2; j >= 0; --j) { suffix[j] = max(suffix[j], suffix[j + 1]); } for (int j = 0; j <= m; ++j) { diff[i + 1][j] = max({ j > 0 ? maxi - prefix[j - 1] : INT_MIN, j < m ? suffix[j] - mini : INT_MIN, diff[i][j] }); if (j > 0) { diff[i + 1][j] = min(diff[i + 1][j], diff[i + 1][j - 1]); } } } ans = min(ans, *min_element(diff[n], diff[n] + m + 1)); } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...