Submission #426617

#	Time	Username	Problem	Language	Result	Execution time	Memory
426617		milleniumEeee	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	40 / 100	1069 ms	5312 KiB

Main

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

using namespace std;

const int MAXN = (int)2e5 + 5;
const int INF = 1e18;

int a[MAXN];
int arr[MAXN];

signed main() {
	fastInp;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int ans = INF;
	for (int k = 1; k <= n; k++) {
		for (int j = 1; j <= n; j++) {
			a[j] = arr[j];
		}
		int cur_ans = 0;
		int l = k - 1;
		int r = k + 1;
		while (1) {
			while (1 <= l && a[l] < a[l + 1]) {
				l--;
			}
			while (r <= n && a[r - 1] > a[r]) {
				r++;
			}
			if (l == 0 && r == n + 1) {
				chmin(ans, cur_ans);
				break;
			}
			if (l >= 1 && r <= n) {
				int min_diff = min(a[l] - a[l + 1], a[r] - a[r - 1]); 
				cur_ans += min_diff + 1;
				a[l + 1] += min_diff + 1; 
				a[r - 1] += min_diff + 1;
			}
			else if (l == 0) {
				int diff = a[r] - a[r - 1];
				cur_ans += diff + 1;
				a[r - 1] += diff + 1;
			}
			else if (r == n + 1) {
				int diff = a[l] - a[l + 1];
				cur_ans += diff + 1;
				a[l + 1] += diff + 1;
			}
		}
	}
	cout << ans << endl;
}

/*
8
12 2 34 85 4 91 29 85

*/

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