Submission #930619

#	Time	Username	Problem	Language	Result	Execution time	Memory
930619		mocha	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	1 ms	6492 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 2e5+5;

int n;
int a[mx], b[mx], c[mx];
int dp[2][mx];

signed main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n;
	for (int i=0;i<n;i++) {
		cin >> a[i];
	}
	dp[0][0] = 0; b[0] = a[0];
	for (int i=1;i<n;i++) {
		if (a[i] > b[i-1]) {
		   dp[0][i] = dp[0][i-1];
		   b[i] = a[i];
		} else {
		   b[i] = b[i-1]+1;
		   dp[0][i] = dp[0][i-1];
		   if (b[i]-a[i] > b[i-1]-a[i-1]) {
			  dp[0][i] += b[i]-a[i]-b[i-1]+a[i-1];
		   } 
		}	   		   
	}
	dp[1][n-1] = 0;c[n-1] = a[n-1];
	for (int i=n-1;i>=0;i--) {
		if (a[i] > c[i+1]) {
		   dp[1][i] = dp[1][i+1];
		   c[i] = a[i];
		} else {
		   c[i] = c[i+1]+1;
		   dp[1][i] = dp[1][i+1];
		   if (c[i]-a[i] > c[i+1]-a[i+1]) {
			  dp[1][i] += c[i]-a[i]-c[i+1]+a[i+1];
		   } 
		}	   		   
	}

	long long ans = min(dp[0][n-1],dp[1][0]);

	for (int i=1;i<n-1;i++) {
		if (b[i]>c[i+1]) {
			ans = min(ans,
				   	dp[0][i]+dp[1][i+1]-min(b[i]-a[i],c[i+1]-a[i+1]));
		} else {
			ans = min(ans,
				dp[0][i-1]+dp[1][i]-min(b[i-1]-a[i-1],c[i]-a[i]));
		}
	}
	cout << ans << "\n";	
			
}

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