Submission #602951

#	Time	Username	Problem	Language	Result	Execution time	Memory
602951		Apiram	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	0 / 100	0 ms	212 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>diff;
	for (int i = 1;i<n;++i){
		diff.push_back(arr[i - 1] - arr[i]);
	}	
	vector<long long>pref(n + 1,0);
	vector<long long>suff_max(n + 1,0),pref_max(n + 1,0);
	pref[0] = 0;
	for (int i = 0;i<n - 1;++i){
		pref[i + 1] = pref[i] + max(0LL,diff[i] + 1);
		pref_max[i + 1] = max(pref_max[i],max(0LL,diff[i] + 1));
	}
	vector<long long>suff(n + 1,0);
	suff[n - 1] = 0;
	for (int i = n - 1;i>=1;--i){
		suff[i - 1] = suff[i] + max(0LL,-(diff[i - 1] - 1));
		suff_max[i - 1] = max(suff_max[i],max(0LL,-(diff[i - 1] - 1)));
	}
	long long ans = 1e15;
	for (int i = 0;i<n - 1;++i){
		ans = min(ans,pref[i] + suff[i + 1] - min(pref_max[i],suff_max[i + 1]));
	}
	cout<<ans<<'\n';
	return 0;
}

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