Submission #372644

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

Main

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

ll A[N];

ll p[N], s[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];
	/*for (int i = 1 ; i <= n ; ++ i) {
		vector<int>b(n+1);
		for (int j = 1 ; j <= n ; ++ j) b[j] = A[j];
		ll L = 0, R = 0;
		for (int j = 1 ; j < i ; ++ j) {
			while (b[j + 1] <= b[j]) b[j + 1]++, L++;
		}
		for (int j = n ; j > i ; -- j) {
			while (b[j - 1] <= b[j]) b[j - 1]++, R++;
		}
		ll cur = max(L, R);
		for (int j = 1 ; j <= n ; ++ j) {
			cout << b[j] << " ";
		}
		cout << ": " << cur << "\n";
	}*/
	ll val = 0;
	for (int i = 1 ; i <= n ; ++ i) {
		ll add = max(0ll, val + 1 - A[i]);
		val = max(val, A[i]);
		p[i] = p[i - 1] + add;
	}
	val = 0;
	for (int i = n ; i >= 1 ; -- i) {
		ll add = max(0ll, val + 1 - A[i]);
		val = max(val, A[i]);
		s[i] = s[i + 1] + add;
	}
	ll ans = ll(1e18);
	for (int i = 1 ; i <= n + 1 ; ++ i) {
		ans = min(ans, max(p[i - 1], s[i]));
	//	cout << p[i] << ' ';
	}
	/*cout << "\n";
	for (int i = 1 ; i <= n ; ++ i) cout << s[i] << " ";
	cout << "\n";
	*/cout << ans;
}

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