제출 #386928

#제출 시각아이디문제언어결과실행 시간메모리
386928lukameladzeGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
95 ms10348 KiB
# include <bits/stdc++.h> #define f first #define s second #define pb push_back using namespace std; const int N=1e6+5; long long n,a[N],dp[N],pre,a1[N],dp1[N],a2[N],ans; vector <long long> v; int main() { cin>>n; for (int i=1; i<=n; i++) { cin>>a[i]; a1[i]=a[i]; a2[i]=a[i]; } for (int i=1; i<=n; i++) { a1[i]+=pre; //cout<<a1[i]<<" "<<a1[i-1]<<endl; if(a1[i]<=a1[i-1]) { pre+=abs(a1[i-1]-a1[i])+1LL; a1[i]=a1[i-1]+1; } dp[i]=pre; // cout<<a1[i]<<" "; //cout<<dp[i]<<" "; //cout<<a1[i]<<" "; } // cout<<endl; //for (int i=1; i<=n; i++) //cout<<dp[i]<<" "; //cout<<endl; pre=0; for (int i=n; i>=1; i--) { a2[i]+=pre; if (a2[i]<=a2[i+1]) { pre+=abs(a2[i+1]-a2[i])+1LL; a2[i]=a2[i+1]+1; } dp1[i]=pre; // cout<<dp1[i]<<" "; } // cout<<endl; ans=min(dp[n],dp1[1]); for (int i=1; i<n; i++) { //cout<<dp[i]<<" "<<dp[i+1]<<endl; long long anss=max(dp[i],dp1[i+1]); if (a1[i]+anss==a2[i+1]+anss) ans=min(ans,max(dp[i],dp1[i+1])+1); else ans=min(ans,max(dp[i],dp1[i+1])); } cout<<ans<<endl; // for (int i=1; i<=n; i++) { // cout<<dp[i]<<" "<<dp1[i+1]<<endl; //} }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...