Submission #1326548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326548		tkm_algorithms	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	0 ms	332 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;

void solve() {
	int n; cin >> n;
	vector<int> a(n+2);
	rep(i, 1, n+1)cin >> a[i];
	
	vector<int> inc(n+1), dec(n+2);
	inc[1] = a[1], dec[n] = a[n];
	int mx1 = a[1], mx2 = a[n];
	rep(i, 2, n+1) {
		inc[i] = max(a[i], mx1+1);
		mx1 = max(mx1, inc[i]);
	}
	
	rep(i, n, 1) {
		dec[i] = max(a[i], mx2+1);
		mx2 = max(mx2, dec[i]);
	}
	
	vector<int> p(n+2), s(n+2);
	rep(i, 2, n+1) {
		int x = inc[i]-a[i];
		if (x <= inc[i-1]-a[i-1])p[i] = 0;
		else p[i] = x-inc[i-1]+a[i-1];
		p[i] += p[i-1];
	}
	
	rep(i, n, 1) {
		//cout << i << " ";
		int x = dec[i]-a[i];
		if (x <= dec[i+1]-a[i+1])s[i] = 0;
		else s[i] = x-dec[i+1]+a[i+1];
		s[i] += s[i+1];
	}
	
	//for (auto i: inc)cout << i << " ";
	//cout << nl;
	//for (auto i: dec)cout << i << " ";
	//cout << nl;
	int res = min(p[n], s[1]);
	//cout << p[n] << " " << s[1] << nl;
	rep(i, 1, n+1) {  // increase till i, decrease after
		int x = max(dec[i], inc[i]);
		int sm = p[i-1]+s[i+1];
		sm += max(0ll, x-a[i]-(inc[i-1]-a[i-1]+dec[i+1]-a[i+1]));
		res = min(res, sm);
		//if (sm == 0)cout << i << nl;
	}
	cout << res << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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