Submission #409113

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

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5; 
const int oo = 2e9;

int val[N];
int a[N];
int f[N];
int n;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
 
	for (int i = 1; i <= n; i++)
		val[i] = max(val[i - 1] + 1, a[i]);
 
	long long cur = 0;
	for (int i = 1; i <= n; i++) 
		f[i] = val[i] - a[i];

	f[n] = max(f[n], f[n - 1]);

	for (int i = 1; i <= n; i++) 
		cur += f[i] - min(f[i], f[i + 1]);

	long long ans = cur;
	// cerr << n << ": ";
	// for (int i = 1; i <= n; i++)
	// 	cerr << f[i] << " \n"[i == n];
 
	for (int i = n - 1; i >= 1; i--) {
		cur -= f[i - 1] - min(f[i - 1], f[i]);
		cur -= f[i] - min(f[i], f[i + 1]);
		cur -= f[i + 1] - min(f[i + 1], f[i + 2]);
		
		val[i + 1] = max(val[i + 2] + 1, a[i + 1]);
		f[i + 1] = val[i + 1] - a[i + 1];
 
		val[i] = max({val[i - 1] + 1, val[i + 1] + 1, a[i]});
		f[i] = val[i] - a[i];

		f[i] = max({f[i], f[i - 1], f[i + 1]});
 	
 		cur += f[i - 1] - min(f[i - 1], f[i]);
		cur += f[i] - min(f[i], f[i + 1]);
		cur += f[i + 1] - min(f[i + 1], f[i + 2]);
		ans = min(ans, cur);
		// cerr << i << ": " << cur << " ";
		// for (int j = 1; j <= n; j++)
		// 	cerr << f[j] << " \n"[j == n];
	}
	cout << ans;
	return 0;
}

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