Submission #581096

#	Time	Username	Problem	Language	Result	Execution time	Memory
581096		chirathnirodha	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	33 ms	5196 KiB

Main

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
void solve(){
    io();
	int n;cin>>n;
	ll a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	ll arr[n],brr[n];
	arr[0]=brr[n-1]=0;
	ll cur=0;
	for(int i=1;i<n;i++){
		if(a[i]<=a[i-1])cur+=a[i-1]-a[i]+1;
		arr[i]=cur;
	}
	cur=0;
	for(int i=n-2;i>=0;i--){
		if(a[i]<=a[i+1])cur+=a[i+1]-a[i]+1;
		brr[i]=cur;
	}
	ll ans=min(arr[n-1],brr[0]);
	for(int i=0;i<n-1;i++){
		ll temp=max(arr[i],brr[i+1]);
		ll x=a[i]+arr[i],y=a[i+1]+brr[i+1];
		if(y>=x)temp+=y-x+1;
		ans=min(ans,temp);
	}
	cout<<ans<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

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