Submission #386802

#	Time	Username	Problem	Language	Result	Execution time	Memory
386802		nikatamliani	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	31 ms	10220 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
ll a[N], s[N], p[N], cost_pref[N], cost_suff[N];
ll n;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[i] = s[i] = a[i];
	}
	ll cnt = 0, cost = 0;
	cost_pref[1] = 0;
	for(int i = 2; i <= n; ++i) {
		p[i] += cnt;
		if(p[i] <= p[i - 1]) {
			cost += p[i - 1] + 1 - p[i];
		}
		cost_pref[i] = cost;
	}
	cnt = cost = 0;
	cost_suff[n] = 0; 
	for(int i = n - 1; i >= 1; --i) {
		s[i] += cnt;
		if(s[i] <= s[i + 1]) {
			cost += s[i + 1] + 1 - s[i];
		}
		cost_suff[i] = cost;
	}
	ll ans = min(cost_suff[1], cost_pref[n]);
	for(int i = 1; i < n; ++i) {
		//i | i + 1
		if(cost_pref[i] == cost_suff[i+1]) {
			ans = min(ans, cost_pref[i] + (p[i] == s[i+1]));
		} else {
			ans = min(ans, max(cost_pref[i], cost_suff[i+1]));
		}
	}
	cout << ans << endl;
}

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