Submission #1219120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219120		trimkus	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	12 ms	468 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;
	if (n == 2) {
		cout << (a[1] == a[0]) << "\n";
		return 0;
	}
	ll res = LLONG_MAX;
	for (int i = 0; i < n; ++i) {
		ll now = 0;
		ll ps = 0, sf = 0;
		auto na = a;
		for (int j = 0; j < i; ++j) {
			now += max(0LL, ps - a[j] + 1);
			na[j] += max(0LL, ps - a[j] + 1);
			ps = max(ps + 1, na[j]);
		}
		for (int j = n - 1; j > i; --j) {
			now += max(0LL, sf - a[j] + 1);
			na[j] += max(0LL, sf - a[j] + 1);
			sf = max(sf + 1, na[j]);
		}
		now += max(0LL, max(ps, sf) - a[i] + 1);
		na[i] += max(0LL, max(ps, sf) - a[i] + 1);
		//~ for (auto& x : na) {
			//~ cout << x << " ";
		//~ }
		now = 0;
		ll add = 0;
		for (int j = 0; j <= n; ++j) {
			if (j == n) {
				now += add;
				continue;
			}
			assert(a[j] <= na[j]);
			if (a[j] != na[j] || j == i) {
				add = max(add, na[j] - a[j]);
			} else {
				now += add;
				add = 0;
			}
		}
		//~ cout << " = " << now << "\n";
		res = min(res, now);
	}
	cout << res << "\n";
	
}

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