Submission #942053

#	Time	Username	Problem	Language	Result	Execution time	Memory
942053		dsyz	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll A[N], arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		A[i] = arr[i];
	}
	ll prefix[N];
	ll cur = 0, add = 0;
	for(ll i = 0;i < N;i++){
		if(i >= 1){
			arr[i] += min(add,(arr[i - 1] + 1) - arr[i]);
			cur += max(0ll,(arr[i - 1] + 1) - arr[i]);
			add += max(0ll,(arr[i - 1] + 1) - arr[i]);
			arr[i] = max(arr[i],arr[i - 1] + 1);
		}
		prefix[i] = cur;
	}
	for(ll i = 0;i < N;i++){ //reset
		arr[i] = A[i];
	}
	ll suffix[N];
	cur = 0;
	add = 0;
	for(ll i = N - 1;i >= 0;i--){
		if(i < N - 1){
			arr[i] += min(add,(arr[i + 1] + 1) - arr[i]);
			cur += max(0ll,(arr[i + 1] + 1) - arr[i]);
			add += max(0ll,(arr[i + 1] + 1) - arr[i]);
			arr[i] = max(arr[i],arr[i + 1] + 1);
		}
		suffix[i] = cur;
	}
	for(ll i = 0;i < N;i++){ //reset
		arr[i] = A[i];
	}
	ll minimum = 1e18;
	minimum = min(minimum,suffix[0]);
	for(ll split = 0;split < N - 1;split++){
		ll extra = max(0ll,(A[split] + prefix[split] + 1) - (A[split+1] + suffix[split+1]));
		minimum = min(minimum,prefix[split] + extra + suffix[split + 1]);
	}
	minimum = min(minimum,prefix[N - 1]);
	cout<<minimum<<'\n';
}

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