Submission #485520

#	Time	Username	Problem	Language	Result	Execution time	Memory
485520		arujbansal	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	29 ms	8536 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e9 + 5;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;

	vector<int> A(N + 2);
	A[0] = A[N + 1] = 0;

	for (int i = 1; i <= N; i++)
		cin >> A[i];

	vector<int> B(A);

	vector<int> pref(N + 2, 0), suf(N + 2, 0);
	for (int i = 1, j = N; i <= N; i++, j--) {
		pref[i] = pref[i - 1];
		suf[j] = suf[j + 1];

		A[i] += pref[i];
		B[j] += suf[j];

		if (A[i] <= A[i - 1]) {
			pref[i] += A[i - 1] - A[i] + 1;
			A[i] = A[i - 1] + 1;
		}

		if (B[j] <= B[j + 1]) {
			suf[j] += B[j + 1] - B[j] + 1;
			B[j] = B[j + 1] + 1;
		}
	}

	int ans = suf[1];

	for (int i = 1; i <= N; i++) {
		int mx = max(pref[i], suf[i + 1]);
		// cout << i << " " << mx << "\n";
		// cout << A[i] << " " << B[i + 1] << "\n\n";
		ans = min(ans, mx + (A[i] == B[i + 1] ? A[i] == B[i + 1] : 0));
	}

	cout << ans;
}

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