Submission #1219134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219134		trimkus	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	48 ms	5056 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	for (auto& x : a) cin >> x;
	vector<ll> ps(n), sf(n);
	for (int i = 1; i < n; ++i) {
		ps[i] = ps[i - 1];
		if (a[i - 1] >= a[i]) {
			ps[i] += a[i - 1] - a[i] + 1;
		}
	}
	for (int i = n - 2; i >= 0; --i) {
		sf[i] = sf[i + 1];
		if (a[i + 1] >= a[i]) {
			sf[i] += a[i + 1] - a[i] + 1;
		}
	}
	ll res = LLONG_MAX;
	for (int i = 0; i < n; ++i) {
		res = min(res, max(sf[i], ps[i]));
	}
	cout << res << "\n";
	
}

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