Submission #1135589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135589		nuutsnoynton	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	46 ms	1976 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e5 + 2;
pair < ll, ll > P[N];
int main() {
	ll n, m, r, lo, mid, hi, x, y, i, j, s, mn, ans, t, mx, can = 0, sum;

	cin >> n;
	
	ll a[n + 2], b[n + 2];
	for (i = 1; i <= n; i ++) cin >> a[i];
	ans =LONG_MAX;
	lo = 2;
	hi =n - 1;
	while ( a[lo] > a[lo - 1]) lo ++;
	while ( a[hi] > a[hi +1]) hi --;
	ans = 0;
	while ( lo <= hi) {
		s = a[lo - 1]  +1- a[lo];
		r = a[hi + 1] + 1- a[hi];
		s = min(s, r);
		ans += s;
		a[lo - 1] -= s;
		a[hi + 1] -= s;
		while ( a[lo] > a[lo - 1]) lo ++;
		while ( a[hi] > a[hi +1]) hi --;
	}
	if ( a[lo] == a[hi] && lo - 1 == hi) ans ++;
	cout << ans << endl;
	
}

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