Submission #381749

#	Time	Username	Problem	Language	Result	Execution time	Memory
381749		sofapuden	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	103 ms	2028 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
	ll n; cin >> n;
	vector<ll> v(n);
	for(auto &x : v)cin >> x;
	if(n == 2){
		if(v[0] == v[1]){
			cout << 1 << "\n";
		}
		else cout << 0 << "\n";
		return 0;
	}
	ll l = 1, r = n-2;
	ll ans = 0;
	while(l <= r){
		while(l <= n-1 && v[l] > v[l-1])l++;
		while(r >= 0 && v[r] > v[r+1])r--;
		if(l > r)break;
		ll x = min(v[r+1]-v[r]+1,v[l-1]-v[l]+1);
		v[l-1]-=x;
		v[r+1]-=x;
		ans+=x;
	}
	if(abs(l-r) == 1)ans++;
	cout << ans << "\n";
}

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