Submission #677463

#TimeUsernameProblemLanguageResultExecution timeMemory
677463LucaLucaMMaxcomp (info1cup18_maxcomp)C++17
100 / 100
153 ms21312 KiB
#include <bits/stdc++.h> using namespace std; int n, m; int a[1001][1001]; int dp[1001][1001]; /// dp[n][m] = minim - d pana la (n, m) (dp[n][m] = minim) int b[1001][1001]; void rotire() { int r = 1, c = 1; for (int j=m; j>0; j--) { for (int i=1; i<=n; i++) { if (c > n) r++, c = 1; b[r][c] = a[i][j]; c++; } } swap(n, m); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) a[i][j] = b[i][j]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) cin >> a[i][j]; } int ans = -1; for (int rep=0; rep<4; rep++) { for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) dp[i][j] = a[i][j] + 1; } for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { if (i > 1) { dp[i][j] = min(dp[i][j], dp[i-1][j]+1); dp[i][j] = min(dp[i][j], a[i-1][j] +2); } if (j > 1) { dp[i][j] = min(dp[i][j], dp[i][j-1]+1); dp[i][j] = min(dp[i][j], a[i][j-1]+2); } ans = max(ans, a[i][j] - dp[i][j]); } } rotire(); } cout << ans; 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...