Submission #391918

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

Main

#include <bits/stdc++.h>
/*
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
using namespace std;

#define F first
#define S second
#define pb push_back    
#define nl '\n'
#define all(z) (z).begin(), (z).end()
#define sz(x) (int) (x).size()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;

long long n, m, a, b, y, x, k, ti, h;
string s, ss;
char c, ch;
long double db;                                                            
                                                                           
const int N = 1e5 + 7;                                                     
const int INF = INT_MAX;                                                   
int mod = 1e9 + 7;            

void Main() {
	cin >> n;
	vector<ll> v(n), pref(n, 0), suff(n, 0), temp, pre(n, 0), suf(n, 0), mxp(n, 0), mxs(n, 0);
	for (int i = 0; i < n; ++i) cin >> v[i];
	temp = v;
	mxp[0] = v[0];
	for (int i = 1; i < n; ++i) {
		pref[i] = temp[i - 1] + 1 - temp[i];
		pref[i] = max(pref[i], (ll)0);
		temp[i] = max(temp[i], temp[i - 1] + 1);
		mxp[i] = temp[i];
	}
	temp = v;
	mxs[n - 1] = v[n - 1];
	for (int i = n - 2; i >= 0; --i) {
		suff[i] = temp[i + 1] + 1 - temp[i];
		suff[i] = max(suff[i], (ll)0);
		temp[i] = max(temp[i], temp[i + 1] + 1);
		mxs[i] = temp[i];
	}
	for (int i = 1; i < n; ++i) {
		pre[i] = pre[i - 1];
		if (pref[i] > pref[i - 1]) {
			pre[i] += (pref[i] - pref[i - 1]);
		}
	}
	for (int i = n - 2; i >= 0; --i) {
		suf[i] = suf[i + 1];
		if (suff[i] > suff[i + 1]) {
			suf[i] += (suff[i] - suff[i + 1]);
		}
	}
	ll ans = LLONG_MAX;

	for (int k = 0; k < n; ++k) {
		if (k == 0) {
			ans = min(ans, suf[k]);
		}
		else {
			ll cur = max(pre[k - 1], suf[k]);
			if (mxp[k - 1] + 1 > mxs[k]) {
				cur += mxp[k - 1] + 1 - mxs[k];
			}
			ans = min(ans, cur);
		}
	}
	ans = min(ans, pre[n - 1]);
	cout << ans;
	return;
}

int main () {                                                                           
    IOS;
#ifdef BATYA
    freopen(".in", "r", stdin);
#endif
	Main();
	return 0;	
}

//doner           	 

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