Submission #602962

#TimeUsernameProblemLanguageResultExecution timeMemory
602962ApiramGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
31 ms10564 KiB
#include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<long long>arr(n); for (int i = 0;i<n;++i){ cin>>arr[i]; } vector<long long>diff; for (int i = 1;i<n;++i){ diff.push_back(arr[i - 1] - arr[i]); } vector<long long>pref(n + 1,0); vector<long long>suff_max(n + 1,0),pref_max(n + 1,0); pref[0] = 0; for (int i = 0;i<n - 1;++i){ pref[i + 1] = pref[i] + max(0LL,diff[i] + 1); } vector<long long>suff(n + 1,0); suff[n - 1] = 0; for (int i = n - 1;i>=1;--i){ suff[i - 1] = suff[i] + max(0LL,-(diff[i - 1] - 1)); } long long ans = 1e15; for (int i = 0;i<n;++i){ ans = min(ans,max(pref[i],suff[i])); } cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...