Submission #963336

#TimeUsernameProblemLanguageResultExecution timeMemory
963336biankMaxcomp (info1cup18_maxcomp)C++14
100 / 100
96 ms21024 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) int(x.size()) #define all(x) begin(x),end(x) const int INF = 2e9; int solve(vector<vector<int>> &a) { int n = sz(a), m = sz(a[0]); vector<vector<int>> dp1(n, vector<int>(m)); vector<vector<int>> dp2(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp1[i][j] = -a[i][j] + i + j - 1; dp2[i][j] = a[i][j] + i + j - 1; if (i != 0) { dp1[i][j] = max(dp1[i][j], dp1[i - 1][j]); dp2[i][j] = max(dp2[i][j], dp2[i - 1][j]); } if (j != 0) { dp1[i][j] = max(dp1[i][j], dp1[i][j - 1]); dp2[i][j] = max(dp2[i][j], dp2[i][j - 1]); } } } int ans = -INF; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ans = max({ans, a[i][j] - i - j + dp1[i][j], -a[i][j] - i - j + dp2[i][j]}); } } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } int ans = solve(a); for (int i = 0; i < n; i++) { reverse(all(a[i])); } ans = max(ans, solve(a)); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...