Submission #922999

#TimeUsernameProblemLanguageResultExecution timeMemory
922999IanisMaxcomp (info1cup18_maxcomp)C++17
100 / 100
93 ms17228 KiB
#ifdef LOCAL #include <iostream> #include <fstream> #include <iomanip> #include <cassert> #include <random> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #else #pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> #define cerr if (false) cerr #define endl '\n' #endif #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define lsb(x) (x & (-x)) #define bit(mask, i) (((mask) >> (i)) & 1) #define popcount(x) __builtin_popcount(x) #define YES cout << "YES" << endl #define NO cout << "NO" << endl using namespace std; template <typename T> bool ckmax(T &a, T b) { return a < b ? a = b, true : false; } template <typename T> bool ckmin(T &a, T b) { return a > b ? a = b, true : false; } using ll = long long; using pii = pair<int, int>; const int NMAX = 1005; const int INF = 1e9+5; int n, m; int a[NMAX][NMAX]; int dp[NMAX][NMAX]; void read() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin >> a[i][j]; } } void reset() { for (int i = 0; i <= n + 1; i++) fill(dp[i], dp[i] + m + 2, INF); } int solve() { int ans = -1; reset(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = a[i][j] + 1; ckmin(dp[i][j], min(dp[i - 1][j], dp[i][j - 1]) + 1); ckmax(ans, a[i][j] - dp[i][j]); } } reset(); for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { dp[i][j] = a[i][j] + 1; ckmin(dp[i][j], min(dp[i - 1][j], dp[i][j + 1]) + 1); ckmax(ans, a[i][j] - dp[i][j]); } } reset(); for (int i = n; i >= 1; i--) { for (int j = 1; j <= m; j++) { dp[i][j] = a[i][j] + 1; ckmin(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]) + 1); ckmax(ans, a[i][j] - dp[i][j]); } } reset(); for (int i = n; i >= 1; i--) { for (int j = m; j >= 1; j--) { dp[i][j] = a[i][j] + 1; ckmin(dp[i][j], min(dp[i + 1][j], dp[i][j + 1]) + 1); ckmax(ans, a[i][j] - dp[i][j]); } } return ans; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { read(); cout << solve() << 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...