Submission #382790

#	Time	Username	Problem	Language	Result	Execution time	Memory
382790		ritul_kr_singh	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	33 ms	10172 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, ans = 1e18; cin >> n;
	int a[n];
	for(int &i : a) cin >> i;

	array<int, 2> dp0[n], dp1[n];
	dp0[0] = {0, a[0]}; // cost, ending
	dp1[n-1] = {0, a[n-1]};
	for(int i=1; i<n; ++i){
		int x = dp0[i-1][0], y = dp0[i-1][1];
		if(y < a[i] + x) dp0[i] = {x, a[i]+x};
		else dp0[i] = {x + y + 1LL - (a[i]+x), y + 1LL};
		x = dp1[n-i][0], y = dp1[n-i][1];
		if(a[n-i-1] + x > y) dp1[n-i-1] = {x, a[n-i-1] + x};
		else dp1[n-i-1] = {x + y + 1LL - (a[n-i-1]+x), y + 1LL};
	}

	for(int i=0; i<n; ++i){
		// cout << a[i] sp dp0[i][0] sp dp0[i][1] nl;
		ans = min(ans, max(dp0[i][0], dp1[i][0]));
	}
	cout << ans;
}

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