Submission #521122

#	Time	Username	Problem	Language	Result	Execution time	Memory
521122		new_acc	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	30 ms	3908 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=2e5+10;
ll t[N];
void solve(){
	int n;
	cin>>n;
	rep(i,n) cin>>t[i];
	ll naj1=0,naj2=0,res=0;
	rep(i,n-1) naj1+=max(0LL,t[i+1]-t[i]+1);
	res=naj1;
	for(int i=1;i<=n-1;i++){
		naj1-=max(0LL,t[i]-t[i-1]+1),naj2+=max(0LL,t[i-1]-t[i]+1);
		res=min(res,max(naj1,naj2));
	}
	naj2=0;
	for(int i=1;i<n;i++) naj2+=max(0LL,t[i-1]-t[i]+1);
	res=min(res,naj2);
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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