Submission #949624

#	Time	Username	Problem	Language	Result	Execution time	Memory
949624		amirhoseinfar1385	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	23 ms	8076 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long n,all[maxn];
long long ps[maxn],suf[maxn],dpps[maxn],dpsuf[maxn];
void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
}

void pre(){
	for(long long i=1;i<=n;i++){
		ps[i]=ps[i-1];
		ps[i]+=max(0ll,all[i-1]-all[i]+1);
	}
	for(long long i=n;i>=1;i--){
		suf[i]=suf[i+1];
		suf[i]+=max(0ll,all[i+1]-all[i]+1);
	}
}

void solve(){
	long long res=1e15;
	for(long long i=1;i<=n;i++){
		//cout<<i<<" "<<ps[i]<<" "<<suf[i]<<endl;
		long long fres=max(ps[i],suf[i]);
		res=min(res,fres);
	}
	cout<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

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