Submission #389068

#	Time	Username	Problem	Language	Result	Execution time	Memory
389068		prvocislo	Fireworks (APIO16_fireworks)	C++17	0 / 100	2 ms	1228 KiB

fireworks

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;

const int maxi = 307, inf = 1e9 + 79;
vector<vector<int> > dp(maxi, vector<int>(maxi, inf));
vector<vector<pair<int, int> > > g(maxi);
int n, m;
void dfs(int u, ll dist)
{
	if (dist >= maxi)
	{
		cout << dp[inf][inf] << "\n";
		exit(0);
	}
	if (u >= n)
	{
		dp[u][0] = 0;
		return;
	}
	for (int i = 0; i < maxi; i++) dp[u][i] = 0;
	for (pair<int, int> v : g[u])
	{
		dfs(v.first, dist + (ll)v.second);
		vector<int> dp2(maxi, inf);
		for (int j = 0; j < maxi - v.second; j++) dp2[j + v.second] = dp[v.first][j];
		for (int i = 1; i < maxi; i++) dp2[i] = min(dp2[i], dp2[i - 1] + 1);
		for (int i = maxi - 2; i >= 0; i--) dp2[i] = min(dp2[i], dp2[i + 1] + 1);
		for (int i = 0; i < maxi; i++) dp[u][i] += dp2[i];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1, p, c; i < n + m; i++)
	{
		cin >> p >> c;
		g[--p].push_back({ i, c });
	}
	dfs(0, 0);
	cout << *min_element(dp[0].begin(), dp[0].end()) << "\n";
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45