Submission #696321

#	Time	Username	Problem	Language	Result	Execution time	Memory
696321		yaufung	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	0 ms	212 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	long long ans = 0;
	vector<long long> a(n + 1);
	vector<bool> b(n + 1, false);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = 2, r = n - 1;
	while (l <= n && a[l] > a[l - 1]) l++;
	while (r >= 1 && a[r] > a[r + 1]) r--;
	if (l > n || r < 1) {
		cout << "0\n";
		return 0;
	}
	
	while (l <= r) {
		long long add = min(abs(a[l] - a[l - 1]), abs(a[r] - a[r + 1])) + 1;
		a[l] += add;
		a[r] += add;
		ans += add;
		while (l <= n && a[l] > a[l - 1]) {
			l++;
			if (!b[l]) {
				b[l] = true;
				a[l] += ans;
			}
		}
		while (r >= 1 && a[r] > a[r + 1]) {
			r--;
			if (!b[r]) {
				b[r] = true;
				a[r] += ans;
			}
		}
	}
	if (l <= n && r >= 1 && a[l] == a[r]) ans++;
	cout << ans << endl;
	return 0;
}

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