Submission #1165209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165209		pinbu	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	20 ms	6804 KiB

Main

#include<bits/stdc++.h>

#define fi first
#define se second
#define int long long
#define sz(v) (int)v.size()

using namespace std;

const int MAXN = 2e5 + 5;

int n,a[MAXN], prefix[MAXN], suffix[MAXN];

signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	vector<int> diff;
	for (int i = 1;i < n;i++) {
		diff.push_back(a[i] - a[i + 1]);
	}

	if (diff[0] >= 0) prefix[0] = diff[0] + 1;
	else prefix[0] = 0;
	
	for (int i = 1;i < sz(diff);i++) {
		if (diff[i] >= 0) prefix[i] = prefix[i - 1] + diff[i] + 1;
		else prefix[i] = prefix[i - 1];
	}
	
	if (diff[sz(diff) - 1] <= 0) suffix[sz(diff) - 1] = abs(diff[sz(diff) - 1]) + 1;
	else suffix[sz(diff) - 1] = 0;
	for (int i = sz(diff) - 2;i >= 0;i--) {
		if (diff[i] <= 0) suffix[i] = suffix[i + 1] + abs(diff[i]) + 1;
		else suffix[i] = suffix[i + 1];
	}
	// ---- ++++
	int ans = 1e18;
	for (int i = 0;i <= sz(diff);i++) {
		int p = (i == 0) ? 0 : prefix[i - 1];
		int s = suffix[i];
		ans = min(ans, max(p,s));
	}
	cout << ans;
	
	return 0;
}

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