Submission #381239

#	Time	Username	Problem	Language	Result	Execution time	Memory
381239		limabeans	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	34 ms	7268 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
ll a[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;

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

    a[n+1]=a[0]=0;

    vector<ll> d;
    for (int i=1; i<=n+1; i++) {
	d.push_back(a[i]-a[i-1]);
    }

    // iterate over last positive number
    n = d.size();
    vector<ll> suf(n+10);
    for (int i=n-1; i>=0; i--) {
	suf[i]=suf[i+1];
	if (d[i]>=0) {
	    suf[i] += (d[i]+1);
	}
    }

    ll res = 1e18;
    ll pre = 0;
    for (int i=0; i<n; i++) {
	if (d[i]<=0) {
	    pre += (abs(d[i])+1);
	}
	ll cur = max(pre,suf[i+1]);
	res = min(res, cur);
    }
    
    out(res);    
    return 0;
}

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