Submission #433441

#	Time	Username	Problem	Language	Result	Execution time	Memory
433441		xuliu	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1 ms	332 KiB

Main

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

#define ll long long
#define ull unsigned LL
#define ld long double
#define debug if(0)
#define fastio ios_base::sync_with_stdio(0); cin.tie()

const int INF = 1e9 + 4;

int main() {
	fastio;
	int n;
	cin>>n;
	vector<ll> a(n, 0), b(n, 0);
	for(int i=0; i<n; i++)
		cin>>a[i];
	for(int i=1; i<n; i++)
		b[i] = a[i]-a[i-1];
	vector<ll> l(n, 0), r(n, 0);
	l[0] = 0;
	for(int i=1; i<n; i++)
		l[i] = l[i-1] + (b[i] > 0 ? 0 : abs(b[i])+1);
	r[n-1] = 0;
	for(int i=n-2; i>=0; i--)
		r[i] = r[i+1] + (b[i+1] < 0 ? 0 : abs(b[i+1])+1);
	debug {
		cerr<<"l: ";
		for(int i=0; i<n; i++)
			cerr<<l[i]<<" ";
		cerr<<"\nr: ";
		for(int i=0; i<n; i++)
			cout<<r[i]<<" ";
		cerr<<"\n";
	}
	ll ans = INF;
	for(int i=0; i<n; i++)
		ans = min(ans, max(l[i], r[i]));
	cout<<ans;
}

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