Submission #380220

#	Time	Username	Problem	Language	Result	Execution time	Memory
380220		peijar	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	492 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbFleurs;
	cin >> nbFleurs;
	vector<int> fleurs(nbFleurs);
	for (auto &v : fleurs)
		cin >> v;

	vector<int> costPrefix(nbFleurs), costSuffix(nbFleurs);
	vector<int> valFinalePrefix(nbFleurs), valFinaleSuffix(nbFleurs);
	costPrefix[0] = 0;
	valFinalePrefix[0] = fleurs[0];
	int prv(fleurs[0]), nbUp(0);
	for (int iFleurs = 1; iFleurs < nbFleurs; ++iFleurs) 
	{
		int nbNecessaires = max(0LL, prv + 1 - fleurs[iFleurs] - nbUp);
		nbUp = nbNecessaires;
		costPrefix[iFleurs] = costPrefix[iFleurs-1] + nbUp;
		prv = max(prv+1, fleurs[iFleurs]);
		valFinalePrefix[iFleurs] = prv;
	}
	
	prv = fleurs.back(), nbUp = 0;
	costSuffix.back() = 0;
	valFinaleSuffix.back() = fleurs.back();

	for (int iFleurs(nbFleurs-2); iFleurs >= 0; --iFleurs)
	{
		int nbNecessaires = max(0LL, prv + 1 - fleurs[iFleurs] - nbUp);
		nbUp = nbNecessaires;
		costSuffix[iFleurs] = costSuffix[iFleurs+1] + nbUp;
		prv = max(prv+1, fleurs[iFleurs]);
		valFinaleSuffix[iFleurs] = prv;
	}

	int sol(1e18);

	for (int iMax(0); iMax < nbFleurs; ++iMax)
	{
		int cout(0);
		if (valFinalePrefix[iMax] < valFinaleSuffix[iMax])
			cout = max(costSuffix[iMax], (iMax ? costPrefix[iMax-1] : 0));
		else
			cout = max(costPrefix[iMax], (iMax < nbFleurs-1 ? costSuffix[iMax+1] : 0));
		sol = min(sol, cout);
	}
	cout << sol << endl;
}

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