Submission #494708

#TimeUsernameProblemLanguageResultExecution timeMemory
494708dannyboy20031204Maxcomp (info1cup18_maxcomp)C++17
100 / 100
132 ms16948 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define mp make_pair using namespace std; void db() {cout << endl;} template <typename T, typename ...U> void db(T a, U ...b) { //return; cout << a << ' ', db(b...); } #ifdef Cloud #define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #else #define file ios::sync_with_stdio(false); cin.tie(0) #endif const int N = 3001; signed main(){ file; int n, m; cin >> n >> m; int a[n][m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j]; int mi[n][m], ans = -1; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (!i and !j) mi[i][j] = a[i][j] - i - j; else if (!i) mi[i][j] = min(mi[i][j - 1], a[i][j] - i - j); else if (!j) mi[i][j] = min(mi[i - 1][j], a[i][j] - i - j); else mi[i][j] = min({mi[i - 1][j], mi[i][j - 1], a[i][j] - i - j}); ans = max(ans, a[i][j] - i - j - mi[i][j] - 1); } } //db(ans); for (int i = 0; i < n; i++){ for (int j = m - 1; j >= 0; j--){ if (!i and j == m - 1) mi[i][j] = a[i][j] - i + j; else if (!i) mi[i][j] = min(mi[i][j + 1], a[i][j] - i + j); else if (j == m - 1) mi[i][j] = min(mi[i - 1][j], a[i][j] - i + j); else mi[i][j] = min({mi[i - 1][j], mi[i][j + 1], a[i][j] - i + j}); ans = max(ans, a[i][j] - i + j - mi[i][j] - 1); } } for (int i = n - 1; i >= 0; i--){ for (int j = 0; j < m; j++){ if (i == n - 1 and !j) mi[i][j] = a[i][j] + i - j; else if (i == n - 1) mi[i][j] = min(mi[i][j - 1], a[i][j] + i - j); else if (!j) mi[i][j] = min(mi[i + 1][j], a[i][j] + i - j); else mi[i][j] = min({mi[i + 1][j], mi[i][j - 1], a[i][j] + i - j}); ans = max(ans, a[i][j] + i - j - mi[i][j] - 1); } } for (int i = n - 1; i >= 0; i--){ for (int j = m - 1; j >= 0; j--){ if (i == n - 1 and j == m - 1) mi[i][j] = a[i][j] + i + j; else if (i == n - 1) mi[i][j] = min(mi[i][j + 1], a[i][j] + i + j); else if (j == m - 1) mi[i][j] = min(mi[i + 1][j], a[i][j] + i + j); else mi[i][j] = min({mi[i + 1][j], mi[i][j + 1], a[i][j] + i + j}); ans = max(ans, a[i][j] + i + j - mi[i][j] - 1); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...