Submission #409145

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

long long f[N];
long long g[N];

int a[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 = 2; i <= n; i++)
		f[i] = f[i - 1] + max(0, a[i - 1] - a[i] + 1);

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

	long long ans = 1e18;
	for (int mid = 1; mid <= n; mid++) {
		int cost = max(0, max(a[mid - 1], a[mid + 1]) - a[mid] + 1);
		ans = min(ans, max(f[mid - 1], g[mid + 1]) + cost);
	}
	cout << ans;
 	return 0;
}

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