Submission #1036600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036600		andrewp	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	19 ms	6488 KiB

Main

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

constexpr int N = 1e5 + 20;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	int n;
	cin >> n;
	vector<int> a(n);
	vector<ll> ps(n, 0), ss(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		ps[i] = ps[i - 1];
		if (a[i] <= a[i - 1]) {
			ps[i] += (a[i - 1] - a[i] + 1);
		}
	}
	for (int i = n - 2; i >= 0; i--) {
		ss[i] = ss[i + 1];
		if (a[i] <= a[i + 1]) {
			ss[i] += (a[i + 1] - a[i] + 1);
		}
	}
	ll ans = 1e18;
	for (int i = 0; i < n; i++) {
		ps[i] = max(ps[i], ss[i]);
		ans = min(ans, ps[i]);
	}
	cout << ans << '\n';
}

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