Submission #372635

#	Time	Username	Problem	Language	Result	Execution time	Memory
372635		SeDunion	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	384 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

ll A[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> A[i];
	int L = 1, R = n;
	ll Ladd = 0, Radd = 0;
	ll All = 0;
	while (L < R) {
		while (L < R && A[L] - Ladd < A[L + 1]) Ladd -= max(0ll, A[L] - A[L + 1] + 1), ++L;
		while (L < R && A[R] - Radd < A[R - 1]) Radd -= max(0ll, A[R] - A[R - 1] + 1), --R;
		if (L >= R) break;
		if (L + 1 == R) {
			All += A[L] == A[R] && Ladd == 0 && Radd == 0;
			break;
		}
		ll nLadd = A[L] - Ladd - A[L + 1] + 1;
		ll nRadd = A[R] - Radd - A[R - 1] + 1;
		All += min(nLadd, nRadd);
		if (nLadd <= nRadd) {
			Radd += nLadd;
			++L;
		} else {
			Ladd += nRadd;
			--R;
		}
	}
	cout << All;
}

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