제출 #870616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870616		aaron_dcoder	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	40 / 100	1087 ms	12844 KiB

Main

#undef NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e11;


int main() {
	ll N;
	cin >> N;

	vector<ll> A(N);
	
	for (ll i = 0; i < N; ++i)
	{
		cin >> A[i];
	}

	vector<ll> prefixinccost(N,-1);
	vector<ll> suffixdeccost(N,-1);

	prefixinccost[0]=0;
	for (ll i = 1; i < N; ++i)
	{
		if (A[i-1]<A[i]) 
		{
			prefixinccost[i] = prefixinccost[i-1];
		} 
		else 
		{
			prefixinccost[i] = prefixinccost[i-1] + (A[i-1]-A[i]+1);
		}
	}

	suffixdeccost[N-1]=0;
	for (ll i = N-2; i >= 0; --i)
	{
		if (A[i]>A[i+1]) 
		{
			suffixdeccost[i] = suffixdeccost[i+1];
		}
		else 
		{
			suffixdeccost[i] = suffixdeccost[i+1] + (A[i+1]-A[i]+1);
		}
	}

	ll outp = max(prefixinccost[0],suffixdeccost[0]);
	for (ll i = 0; i < N; ++i)
	{
		dbg(i << ":" << suffixdeccost[i] << "," << prefixinccost[i]);
		outp = min(outp, max(prefixinccost[i],suffixdeccost[i]));
	}

	cout << outp;


}

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