Submission #197378

#TimeUsernameProblemLanguageResultExecution timeMemory
197378kmekhovichMaxcomp (info1cup18_maxcomp)C++14
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; #define pb push_back #define fst first #define snd second #define all(c) (c).begin(), (c).end() typedef long long ll; typedef long double ld; const ll INF64 = 1e18 + 228; const int INF32 = 1e9 + 1337; const int MOD = 1e9 + 7; const ld eps = 1e-7; const int N = 1e3 + 3; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector< vector<ll> > a(n, vector<ll>(m)); vector< vector<ll> > dp(n, vector<ll>(m, INF64)); for(auto& it : a) for(auto& it2 : it) cin >> it2; ll ans = -INF64; for(int i = 0; i < n + m - 1; i++) { for(int j = 0; j <= i; j++) { int x = j; int y = i - j; if(x >= n || y < 0 || y >= m) continue; dp[x][y] = min(dp[x][y], a[x][y] - x - y); if(x) dp[x][y] = min(dp[x][y], dp[x - 1][y]); if(y) dp[x][y] = min(dp[x][y], dp[x][y - 1]); ans = max(ans, a[x][y] - x - y - dp[x][y] - 1); } } // dp.clear(); // dp.resize(n, vector<ll>(m, INF64)); // for(int i = 0; i < n + m - 1; i++) // { // for(int j = 0; j <= i; j++) // { // int x = j; // int y = i - j; // if(x >= n || y < 0 || y >= m) continue; // dp[x][y] = min(dp[x][y], a[x][y] - x - y); // if(x) // dp[x][y] = min(dp[x][y], dp[x - 1][y]); // if(y) // dp[x][y] = min(dp[x][y], dp[x][y - 1]); // ans = max(ans, a[x][y] - x - y - dp[x][y] - 1); // } // } 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...