제출 #602954

#제출 시각아이디문제언어결과실행 시간메모리
602954ApiramGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
0 / 100
1 ms212 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); pref_max[i + 1] = max(pref_max[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)); suff_max[i - 1] = max(suff_max[i],max(0LL,-(diff[i - 1] - 1))); } long long ans = 1e15; for (int i = 1;i<n - 1;++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...