Submission #386928

#	Time	Username	Problem	Language	Result	Execution time	Memory
386928		lukameladze	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	95 ms	10348 KiB

Main

# 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;
     //}
}

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60