Submission #496851

#TimeUsernameProblemLanguageResultExecution timeMemory
496851abc864197532Maxcomp (info1cup18_maxcomp)C++17
100 / 100
135 ms28448 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define eb emplace_back #define pb push_back #define X first #define Y second #define pii pair<int,int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T i, U ...j) { cout << i << ' ', abc(j...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } #ifdef Doludu #define test(x...) abc("[" + string(#x) + "]", x); #else #define test(x...) void(0); #endif const int N = 1001; int a[N][N], ul[N][N], ur[N][N], dl[N][N], dr[N][N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { cin >> a[i][j]; ul[i][j] = -a[i][j] + i + j; ur[i][j] = -a[i][j] + i - j; dl[i][j] = -a[i][j] - i + j; dr[i][j] = -a[i][j] - i - j; } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (i) ul[i][j] = max(ul[i][j], ul[i - 1][j]); if (j) ul[i][j] = max(ul[i][j], ul[i][j - 1]); } for (int i = 0; i < n; ++i) for (int j = m - 1; ~j; --j) { if (i) ur[i][j] = max(ur[i][j], ur[i - 1][j]); if (j + 1 < m) ur[i][j] = max(ur[i][j], ur[i][j + 1]); } for (int i = n - 1; ~i; --i) for (int j = 0; j < m; ++j) { if (i + 1 < n) dl[i][j] = max(dl[i][j], dl[i + 1][j]); if (j) dl[i][j] = max(dl[i][j], dl[i][j - 1]); } for (int i = n - 1; ~i; --i) for (int j = m - 1; ~j; --j) { if (i + 1 < n) dr[i][j] = max(dr[i][j], dr[i + 1][j]); if (j + 1 < m) dr[i][j] = max(dr[i][j], dr[i][j + 1]); } int ans = -1; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { ans = max(ans, a[i][j] - i - j + ul[i][j] - 1); ans = max(ans, a[i][j] - i + j + ur[i][j] - 1); ans = max(ans, a[i][j] + i - j + dl[i][j] - 1); ans = max(ans, a[i][j] + i + j + dr[i][j] - 1); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...