Submission #372713

#	Time	Username	Problem	Language	Result	Execution time	Memory
372713		SeDunion	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	40 / 100	1093 ms	3436 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

ll A[N], b[N];

int main() { // fuck O(N) all my homies brute for O(N^2)
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> A[i];
	}
	ll ans = ll(1e18);
	for (int i = 1 ; i <= n ; ++ i) { // the highest point
		for (int j = 1 ; j <= n ; ++ j) {
			b[j] = A[j];
		}
		ll L = 0, R = 0; // the number of waterings of the left side and the right side
		for (int j = 1 ; j < i ; ++ j) {
			if (b[j + 1] < b[j] + 1) {
				L += b[j] + 1 - b[j + 1];
			}
		}
		for (int j = n ; j > i ; -- j) {
			if (b[j - 1] < b[j] + 1) {
				R += b[j] + 1 - b[j - 1];
			}
		}
		ans = min(ans, max(L, R));
	}
	cout << ans;
}

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