제출 #531537

#제출 시각아이디문제언어결과실행 시간메모리
531537amunduzbaevGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
29 ms10060 KiB
#include "bits/stdc++.h" using namespace std; #define ar array #define int long long signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<int> a(n), pref(n), pc(n); vector<int> suff(n), sc(n); for(int i=0;i<n;i++) cin>>a[i]; int v = a[0], add = 0; for(int i=1;i<n;i++){ pref[i] = pref[i-1]; if(a[i] > v){ add = 0; } else { if(add < v + 1 - a[i]){ pref[i] += ((v + 1) - a[i] - add); } add = v + 1 - a[i]; } v = max(v + 1, a[i]); pc[i] = add; } v = a[n-1], add = 0; for(int i=n-2;~i;i--){ suff[i] = suff[i+1]; if(a[i] > v){ add = 0; } else { if(add < v + 1 - a[i]){ suff[i] += ((v + 1) - a[i] - add); } add = v + 1 - a[i]; } v = max(v + 1, a[i]); sc[i] = add; } int res = 1e18; for(int i=0;i<n;i++){ res = min(res, max(pref[i], suff[i])); //~ res = min(res, pref[i] + suff[i] - min(pc[i], sc[i])); } //~ for(int i=0;i<n;i++){ //~ cout<<pref[i]<<" "; //~ } cout<<"\n"; //~ for(int i=0;i<n;i++){ //~ cout<<suff[i]<<" "; //~ } cout<<"\n"; //~ for(int i=0;i<n;i++){ //~ cout<<pc[i]<<" "; //~ } cout<<"\n"; //~ for(int i=0;i<n;i++){ //~ cout<<sc[i]<<" "; //~ } cout<<"\n"; cout<<res<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...