Submission #685081

#	Time	Username	Problem	Language	Result	Execution time	Memory
685081		ethening	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	25 ms	10084 KiB

Main

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

int n;
// int spar[200005][20];
// int pwr[20];
ll a[200005];

// void init() {
// 	pwr[0] = 1;
// 	for (int i = 1; i < 20; i++) pwr[i] = pwr[i - 1] * 2;
// 	for (int i = 0; i < n; i++) spar[i][0] = i;
// 	for (int i = 1; i < 20; i++) {
// 		for (int j = 0; j < n; j++) {
// 			int nxt = j + pwr[i - 1];
// 			int dex1 = spar[j][i - 1];
// 			if (nxt >= n) {
// 				spar[j][i] = dex1;
// 				continue;
// 			}
// 			int dex2 = spar[nxt][i - 1];
// 			if (a[dex1] < a[dex2]) spar[j][i] = dex1;
// 			else spar[j][i] = dex2;
// 		}
// 	}
// }

// int get_min(int l, int r) {
// 	if (l == r) {
// 		return l;
// 	}
// 	int diff = r - l + 1;
// 	int lg2 = 0;
// 	while (pwr[lg2 + 1] <= diff) ++lg2;
// 	int dex1 = spar[l][lg2];
// 	int dex2 = spar[r - pwr[lg2] + 1][lg2];
// 	if (a[dex1] < a[dex2]) return dex1;
// 	else return dex2;
// }

ll con1[200005];
ll con2[200005];

ll diff1[200005];
ll diff2[200005];
ll presum[200005];
ll postsum[200005];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		if (i == 0) con1[i] = 0;
		else {
			con1[i] = max(a[i - 1] + 1 - a[i], 0ll);
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i == n - 1) con2[i] = 0;
		else {
			con2[i] = max(a[i + 1] + 1 - a[i], 0ll);
		}
	}

	// for (int i = 0; i < n; i++) {
	// 	cout << "#" << i << " " << con1[i] << " " << con2[i] << endl;
	// }

	for (int i = 0; i < n; i++) {
		if (i == 0) presum[i] = con1[i];
		else presum[i] = presum[i - 1] + con1[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i == n - 1) postsum[i] = con2[i];
		else postsum[i] = postsum[i + 1] + con2[i];
	}

	// for (int i = 0; i < n; i++) {
	// 	cout << "!" << i << " " << presum[i] << " " << postsum[i] << endl;
	// }

	ll ans = 1e18;
	for (int i = 0; i < n; i++) {
		// int pre = s
		// int x = max(con1[i], con2[i]);
		ans = min(ans, max(presum[i], postsum[i]));
	}
	cout << ans << "\n";
}

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