Submission #870457

#	Time	Username	Problem	Language	Result	Execution time	Memory
870457		Maite_Morale	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	62 ms	10580 KiB

Main

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>

ll n,t[MAX],a[MAX],b[MAX];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    t[n-1]=0;
    for(int i=n-2;i>=0;i--){
        t[i]=t[i+1]+max((ll)0,(a[i+1]+1)-a[i]);
    }ll s=0;ll ans=oo;
    for(int i=0;i<n;i++){
       if(i>0)s+=max((ll)0,(a[i-1]+1)-a[i]);
       ans=min(ans,max(s,t[i]));
    }cout<<ans<<"\n";
return 0;
}

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