Submission #1281156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281156		Newtonabc	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	67 ms	6792 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
ll arr[N],pre[N],suf[N],dif[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<n;i++) dif[i]=arr[i+1]-arr[i];
    long long ans=LLONG_MAX;
    for(int i=1;i<n;i++){
        if(dif[i]<=0) pre[i]=-dif[i]+1;
        if(dif[i]>=0) suf[i]=dif[i]+1;
    }
    for(int i=1;i<n;i++) pre[i]+=pre[i-1];
    for(int i=n-1;i>=1;i--) suf[i]+=suf[i+1];
    for(int i=0;i<n;i++) ans=min(ans,max(pre[i],suf[i+1]));
    cout<<ans;
    // cout<<"\n";
    // for(int i=1;i<n;i++) cout<<dif[i] <<" ";
    // cout<<"\n";
    // for(int i=1;i<n;i++) cout<<pre[i] <<" ";
    // cout<<"\n";
    // for(int i=1;i<n;i++) cout<<suf[i] <<" ";
}

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