Submission #389076

#	Time	Username	Problem	Language	Result	Execution time	Memory
389076		prvocislo	Fireworks (APIO16_fireworks)	C++17	19 / 100	171 ms	720 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;
int rek(int u, int dist, int c)
{
	if (u >= n) return abs(c - dist);
	if (dp[u][dist] != inf) return dp[u][dist];
	for (int cl = 0; cl <= dist; cl++)
	{
		int sum = abs(cl - c);
		for (pair<int, int> v : g[u])
			sum += rek(v.first, dist - cl, v.second);
		dp[u][dist] = min(dp[u][dist], sum);
		if (!c) break;
	}
	return dp[u][dist];
}
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 });
	}
	int ans = inf;
	for (int dist = 0; dist < maxi; dist++)
		ans = min(ans, rek(0, dist, 0));
	cout << ans << "\n";
	return 0;
}

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