Submission #230972

#	Time	Username	Problem	Language	Result	Execution time	Memory
230972		peijar	Stove (JOI18_stove)	C++17	50 / 100	60 ms	82664 KiB

stove

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

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 5001;

ll dp[MAXN][MAXN];

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

	int nb_personnes, nb_allumetes;
	cin >> nb_personnes >> nb_allumetes;

	vector<int> arrivees(nb_personnes);
	for (auto &v : arrivees)
		cin >> v;
	arrivees.push_back(arrivees.back()+1);
	for (int k(0); k <= nb_allumetes; ++k)
		dp[nb_personnes][k] = 0;
	for (int id_per(nb_personnes-1); id_per >= 0; --id_per)
	{
		dp[id_per][0] = (ll)1e18;
		for (int nb_allu(1); nb_allu <= nb_allumetes; ++nb_allu)
			dp[id_per][nb_allu] = min(arrivees[id_per+1] - arrivees[id_per] + dp[id_per+1][nb_allu], 
										(nb_allu ? 1 + dp[id_per+1][nb_allu-1] : (ll)1e18));
	}

	cout << dp[0][nb_allumetes] << endl;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50