Submission #1281737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281737		Jawad_Akbar_JJ	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	68 ms	11376 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N], d[N], Pre[N], Suf[N], Mx1[N], Mx2[N], d2[N];

signed main(){
	int n;
	cin>>n;

	for (int i=1;i<=n;i++){
		cin>>a[i];
		Mx1[i] = max(Mx1[i-1] + 1, a[i]);
		d[i] = max(0LL, Mx1[i] - a[i]);
		Pre[i] = Pre[i-1] + d[i] - min(d[i], d[i-1]);
		// cout<<Pre[i]<<' ';
	}
	// cout<<'\n';

	for (int i=n;i>=1;i--){
		Mx2[i] = max(Mx2[i+1] + 1, a[i]);
		d2[i] = max(0LL, Mx2[i] - a[i]);
		Suf[i] = Suf[i+1] + d2[i] - min(d2[i], d2[i+1]);
		// cout<<Suf[i]<<' ';
	}
	// cout<<'\n';

	for (int i=n-1;i>=1;i--){
		Mx1[i] = max(max(Mx1[i-1], Mx2[i+1]) + 1, a[i]);
		d[i] = max(0LL, Mx1[i] - a[i]);
		Pre[i] = Pre[i-1] + d[i] - min(d[i], d[i-1]);
		Pre[n] = min(Pre[n], max(Pre[i], Suf[i+1]));
		// cout<<Mx1[i]<<" "<<d[i]<<" "<<Pre[i]<<'\n';
	}
	// cout<<'\n';

	cout<<Pre[n]<<'\n';

}

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