Submission #768128

#	Time	Username	Problem	Language	Result	Execution time	Memory
768128		NK_	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	23 ms	6984 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;
template<class T> using V = vector<T>;

const ll INF = 1e18;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<ll> A(N); for(auto& x : A) cin >> x;


	V<ll> P(N), S(N);
	P[0] = 0;
	for(int i = 1; i < N; i++) {
		P[i] = P[i-1] + max(A[i-1] - A[i] + 1, 0LL);
	}

	S[N-1] = 0;		
	for(int i = N-2; i >= 0; i--) {
		S[i] = S[i+1] + max(A[i+1] - A[i] + 1, 0LL);
	}

	// for(int i = 0; i < N; i++) {
	// 	cout << P[i] << " | " << S[i] << endl;
	// }		

	ll ans = INF;
	for(int mid = 0; mid < N; mid++) {
		ans = min(ans, max(P[mid], S[mid]));
	}

	cout << ans << nl;
    return 0;
}

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