Submission #645289

#TimeUsernameProblemLanguageResultExecution timeMemory
645289notmeMaxcomp (info1cup18_maxcomp)C++14
0 / 100
1 ms340 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN = 1e3; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int n, m; int a[MAXN][MAXN]; void read() { cin >> n >> m; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) cin >> a[i][j]; } } int maxx = 0; int dp_ul[MAXN][MAXN]; void fill_dp_ul() { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { dp_ul[i][j] = -1; if(j > 1) { dp_ul[i][j] = max(dp_ul[i][j], dp_ul[i][j-1] - 1); dp_ul[i][j] = max(dp_ul[i][j], abs(a[i][j] - a[i][j-1]) - 1); } if(i > 1) { dp_ul[i][j] = max(dp_ul[i][j], dp_ul[i-1][j] - 1); dp_ul[i][j] = max(dp_ul[i][j], abs(a[i][j] - a[i-1][j]) - 1); } maxx = max(maxx, dp_ul[i][j]); } } } int dp_ur[MAXN][MAXN]; void fill_dp_ur() { for (int i = 1; i <= n; ++ i) { for (int j = m; j >= 1; -- j) { dp_ur[i][j] = -1; if(j < m) { dp_ur[i][j] = max(dp_ur[i][j], dp_ur[i][j+1] - 1); dp_ur[i][j] = max(dp_ur[i][j], abs(a[i][j] - a[i][j+1]) - 1); } if(i > 1) { dp_ur[i][j] = max(dp_ur[i][j], dp_ur[i-1][j] - 1); dp_ur[i][j] = max(dp_ur[i][j], abs(a[i][j] - a[i-1][j]) - 1); } maxx = max(maxx, dp_ur[i][j]); } } } int dp_dl[MAXN][MAXN]; void fill_dp_dl() { for (int i = n; i >= 1; -- i) { for (int j = 1; j <= m; ++ j) { dp_dl[i][j] = -1; if(j > 1) { dp_dl[i][j] = max(dp_dl[i][j], dp_dl[i][j-1] - 1); dp_dl[i][j] = max(dp_dl[i][j], abs(a[i][j] - a[i][j-1]) - 1); } if(i < n) { dp_dl[i][j] = max(dp_dl[i][j], dp_dl[i+1][j] - 1); dp_dl[i][j] = max(dp_dl[i][j], abs(a[i][j] - a[i+1][j]) - 1); } maxx = max(maxx, dp_dl[i][j]); } } } int dp_dr[MAXN][MAXN]; void fill_dp_dr() { for (int i = n; i >= 1; -- i) { for (int j = m; j >= 1; -- j) { dp_dr[i][j] = -1; if(j < m) { dp_dr[i][j] = max(dp_dr[i][j], dp_dr[i][j+1] - 1); dp_dr[i][j] = max(dp_dr[i][j], abs(a[i][j] - a[i][j+1]) - 1); } if(i < n) { dp_dr[i][j] = max(dp_dr[i][j], dp_dr[i+1][j] - 1); dp_dr[i][j] = max(dp_dr[i][j], abs(a[i][j] - a[i+1][j]) - 1); } maxx = max(maxx, dp_dr[i][j]); } } } void solve() { int ans = -1; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { for (int x = 1; x <= n; ++ x) { for (int y = 1; y <= m; ++ y) { int maxx = max(a[i][j], a[x][y]); int minn = min(a[i][j], a[x][y]); int s = abs(x - i) + abs(y - j) + 1; ///cout << i << " " << j << ", " << x << ", " << y << " -> " << maxx - minn - s << endl; ans = max(ans, maxx - minn - s); } } } } cout << ans << endl; } int main() { speed(); read(); fill_dp_ul(); fill_dp_dl(); fill_dp_ur(); fill_dp_dr(); cout << maxx << endl; 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...