Submission #1155705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155705		dnnnda	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	14 ms	5088 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;

int a[200005], d[200005];
ll pos[200005], neg[200005], ans=inff;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for(int i=1 ; i<=n ; i++) cin >> a[i];
    for(int i=1 ; i<=n ; i++) d[i]=a[i]-a[i-1];
    for(int i=1 ; i<=n ; i++)
        pos[i]=pos[i-1]+(d[i]<=0 ? 1-d[i] : 0),
        neg[i]=neg[i-1]+(d[i]>=0 ? d[i]+1 : 0);
    for(int i=1 ; i<=n ; i++){
        ans=min(ans,max(pos[i],neg[n]-neg[i]));
    }
    cout << ans << '\n';

    return 0;
}

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