Submission #409126

#	Time	Username	Problem	Language	Result	Execution time	Memory
409126		ngpin04	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	25 ms	352 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;

	for (int mid = 1; mid <= n; mid++) {
		for (int i = 1; i < mid; i++)
			val[i] = max(val[i - 1] + 1, a[i]);

		for (int i = n; i >= mid + 1; i--)
			val[i] = max(val[i + 1] + 1, a[i]);

		val[mid] = max({a[mid], val[mid - 1] + 1, val[mid + 1] + 1});
	
		long long res = 0;

		for (int i = 1; i <= n; i++)
			f[i] = val[i] - a[i];

		f[mid] = max({f[mid], f[mid - 1], f[mid + 1]});

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

	cout << ans;
	// 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