Submission #534788

#	Time	Username	Problem	Language	Result	Execution time	Memory
534788		Cookie197	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	29 ms	5552 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#define ll long long
#define pii pair<int,int> 
#define mp make_pair
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl

ll arr[200005], dif[200005];
int n;
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>arr[i];
    for (int i=2;i<=n;i++) dif[i] = arr[i] - arr[i-1];
    
    ll left = 0, right = 0;
    for (int i=2;i<=n;i++) if (dif[i] >= 0) right += dif[i]+1;
    ll best = max(left, right);

    for (int i=2;i<=n;i++){
        ll orig = dif[i]>=0 ? dif[i]+1 : 0;
        ll _new = dif[i]<=0 ? 1-dif[i] : 0;
        left += _new;
        right -= orig;
        best = min(best, max(left,right));
    }
    cout<<best<<endl;
}

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