제출 #372707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372707		SeDunion	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	35 ms	384 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];
				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];
				b[j - 1] = b[j] + 1;
			}
		}
		ans = min(ans, max(L, R));
	}
	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 = n ; j > i ; -- j) {
			if (b[j - 1] < b[j] + 1) {
				R += b[j] + 1 - b[j - 1];
				b[j - 1] = b[j] + 1;
			}
		}
		for (int j = 1 ; j < i ; ++ j) {
			if (b[j + 1] < b[j] + 1) {
				L += b[j] + 1 - b[j + 1];
				b[j + 1] = b[j] + 1;
			}
		}
		ans = min(ans, max(L, R));
	}
	cout << ans;
}

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