Submission #655677

#TimeUsernameProblemLanguageResultExecution timeMemory
655677happypotatoGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
99 ms6864 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int main() { int n; cin >> n; int a[n + 1], diff[n + 1]; a[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; diff[i] = a[i] - a[i - 1]; } // make diff positive followed be negative ll pre[n + 2], suf[n + 2]; pre[0] = 0; for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + max(1 - diff[i], 0); } suf[n + 1] = 0; for (int i = n; i >= 1; i--) { suf[i] = suf[i + 1] + max(diff[i] - (-1), 0); } ll ans = 1e18; for (int i = 1; i <= n; i++) { ans = min(ans, max(pre[i], suf[i + 1])); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...