Submission #469317

#	Time	Username	Problem	Language	Result	Execution time	Memory
469317		jason7777	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	35 ms	6548 KiB

Main

#pragma GCC optmize ("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define spIO ios::sync_with_stdio(false);cin.tie(0)
#define mem(x,va) memset(x,va,sizeof(x))
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
inline ll inv(ll x, ll MOD = mod)
{
	ll power = MOD - 2, ret = 1;
	while (power)
	{
		if (power & 1)
			(ret *= x) %= MOD;
		power >>= 1;
		(x *= x) %= MOD;
	}
	return ret;
}
inline ll gcd(ll x, ll y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}
ll pow2(ll target, ll p)
{
	ll ret = 1;
	while (p)
	{
		if (p & 1)
			(ret *= target) %= mod;
		p >>= 1;
		(target *= target) %= mod;
	}
	return ret;
}

int n;
ll arr1[200000 + 5], l[200000 + 5], r[200000 + 5], arr2[200000 + 5];
ll maxx = 0, pl;

int main()
{
	spIO;
	cin >> n;
	for0(i, n) cin >> arr1[i];
	for0(i, n) arr2[i] = arr1[i];

	ll acc = 0, ans = 0;
	l[0] = 0;
	for1(i, n - 1)
	{
		if (arr1[i] + acc <= arr1[i - 1])
		{
			ll add = arr1[i - 1] - (arr1[i] + acc) + 1; 
			ans += add;
			acc += add;
			arr1[i] += acc;
		}
		else
			acc = 0;
		l[i] = ans;
		//cout << ans << '\n';
	}
	acc = 0;
	r[n - 1] = 0;
	ans = 0;
	for (int i = n - 2; i >= 0; i--)
	{
		if (arr2[i] + acc <= arr2[i + 1])
		{
			ll add = arr2[i + 1] - (arr2[i] + acc) + 1;
			ans += add;
			acc += add;
			arr2[i] += acc;

			//cout << ans << ' ' << acc << ' ' << arr[i] << '\n';
		}
		else
			acc = 0;
		r[i] = ans;
		//cout << ans << ' ' << acc << '\n';
	}
	ll fans = 2e18;
	for0(i, n)
	{
		fans = min(fans, max(l[i], r[i]));
	}
	//for0(i, n) cout << l[i] << ' '; cout << '\n';
	//for0(i, n) cout << r[i] << ' '; cout << '\n';
	cout << fans << '\n';
}

/*

*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    1 | #pragma GCC optmize ("O3,unroll-loops")
      |

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