Submission #1265774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265774		Mauricio_Cruz	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	0 / 100	0 ms	328 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define ve vector
#define pb push_back
#define vi vector<int>


int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	
	vi a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	
	vi x(n+1,0),y(n+1,0),x1(n+1),y1(n+1);
	
	for(int i=1;i<n;i++){
		int v=a[i-1]+x[i-1]+1;
		v-=a[i];
		x[i]=max(0LL,v);
	}
	for(int i=n-2;i>=0;i--){
		int v=a[i+1]+y[i+1]+1;
		y[i]=max(0LL,v-a[i]);
	}
	x1[0]=x[0];
	y1[n-1]=y[n-1];
	for(int i=1;i<n;i++){
		if(x[i-1]<x[i])x1[i]=x1[i-1]+(x[i]-x[i-1]);
		else x1[i]=x1[i-1];
	}
	for(int i=n-2;i>=0;i--){
		if(y[i+1]<y[i])y1[i]=y1[i+1]+(y[i]-y[i+1]);
		else y1[i]=y1[i+1];
	}	
	int res=min(y1[0],x1[n-1]);
	for(int i=1;i<n-1;i++){
		int v=x[i-1],w=y[i+1];
		int val=min(v,w);
		int r=x1[i-1]+y1[i+1]-val;
		int num=a[i]+val;
		r+=max(0LL,max(a[i-1]+x[i-1]+1,y[i+1]+1)-num);
		res=min(res,r);
	}
	cout<<res;
	/*
	4 5 3 0 0
	3 1 2 4 1
	*/
	
	return 0;
}
/*
9 5 10 9 9 8 11

10 7 12 11 10 9 11


*/

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