제출 #1132368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132368		samek08	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	30 ms	7288 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

const int N = 2e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

ll n;
ll A[N];

void solve()
{
	cin >> n;
	rep(i,n) cin >> A[i];

	vector<ll> pref(n), suf(n);
	vector<ll> R;

	for(int i = 1; i < n; ++i) R.pb(A[i]-A[i-1]);

	ll su = 0;
	rep(i,n-1)
	{
		if(R[i] <= 0) su += -R[i]+1;
		pref[i] = su;
	}

	su = 0;
	for(int i = n-2; i >= 0; --i)
	{
		if(R[i] >= 0) su += R[i]+1;
		suf[i] = su;
	}

	ll ans = INF_L;
	rep(i,n-1)
	{
		ll cost = pref[i];
		if(i+1 < n-1) cost = max(cost,suf[i+1]);
		ans = min(ans,cost);
	}


	ans = min(ans,pref[n-2]);
	ans = min(ans,suf[0]);

	cout << ans << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

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