Submission #377244

#	Time	Username	Problem	Language	Result	Execution time	Memory
377244		YJU	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	29 ms	1904 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,u[N],ans,d;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	REP1(i,n)cin>>u[i];
	if(n==2){cout<<(u[1]==u[2])<<"\n";return 0;}
	ll l=2,r=n-1;
	while(l<=r){
		while(l+1<=r&&u[l]+d>u[l-1])u[l]+=d,++l;
		while(l+1<=r&&u[r]+d>u[r+1])u[r]+=d,--r;
		ll t=min(u[l-1]-(u[l]+d)+1,u[r+1]-(u[r]+d)+1);
		if(t<=0)break;
		d+=t;ans+=t;
	}
	u[l]+=d;
	vector<ll> v={u[l],u[l-1]+1,u[l+1]+1,u[l+1]+2,u[l-1]+2};
	sort(v.begin(),v.end());
	for(auto i:v){
		ll t=max(0LL,i-u[l]);
		ans+=t;
		u[l]+=t;
		if((u[l]>u[l-1]&&u[l]<u[l+1])||(u[l-1]>u[l]&&u[l]>u[l+1])||(u[l]>u[l-1]&&u[l]>u[l+1]))break;
	}
	cout<<ans<<"\n";
	return 0;
}

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