Submission #791222

#TimeUsernameProblemLanguageResultExecution timeMemory
791222n3rm1nGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
20 ms6980 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const long long MAXN = 2e5 + 10; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n; long long a[MAXN]; void read() { cin >> n; for (long long i = 1; i <= n; ++ i) cin >> a[i]; } long long dp0[MAXN], dp1[MAXN]; void solve() { for (long long i = 2; i <= n; ++ i) { dp0[i] = dp0[i-1]; if(a[i] <= a[i-1]) { dp0[i] += a[i-1] + 1 - a[i]; } } for (long long i = n-1; i >= 1; -- i) { dp1[i] = dp1[i+1]; if(a[i] <= a[i+1]) { dp1[i] += a[i+1] + 1 - a[i]; } } long long ans = 1e17+10; for (long long i = 1; i <= n; ++ i) { ans = min(max(dp0[i], dp1[i]), ans); } cout << ans << endl; } int main() { speed(); read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...