Submission #486159

#	Time	Username	Problem	Language	Result	Execution time	Memory
486159		bigDuck	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	24 ms	6976 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
inline char get_ (){
    const int oo=1000005;
    static char buf[oo], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++;
}
int read_ () {
    char c = get_();
    int sum = 0;
    while(!(c >= '0' && c <= '9')) c = get_();
    while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_();
    return sum;
}



int n, a[200010];
int st[200010], dr[200010];


int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>a[i];
}

for(int i=2; i<=n; i++){
    st[i]=st[i-1];
    if(a[i]<(a[i-1]+1) ){
        st[i]+=a[i-1]+1-a[i];
    }
}

for(int i=(n-1); i>=1; i--){
    dr[i]=dr[i+1];
    if(a[i]<(a[i+1]+1) ){
        dr[i]+=a[i+1]+1-a[i];
    }
}

int res=1e18;

for(int i=1; i<=n; i++){
    res=min(max(st[i-1], dr[i+1] )+max(0ll, max(a[i-1]+1, a[i+1]+1)-a[i] ) , res );
}
cout<<res;
return 0;
}

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