Submission #249252

#	Time	Username	Problem	Language	Result	Execution time	Memory
249252		sahil_k	Fireworks (APIO16_fireworks)	C++14	19 / 100	20 ms	1024 KiB

fireworks

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, m;
vector< pair<int, int> > adj[310];
long long dp[310][310];
void dfs (int x) {
	if (adj[x].size() == 0) {
		dp[x][0] = 0;
		for (int i=1; i<=300; i++) {
			dp[x][i] = 1e16;
		}
		return;
	}
	for (auto i: adj[x]) {
		dfs(i.first);
	}
	for (int i=0; i<=300; i++) {
		for (auto j: adj[x]) {
			long long best = 1e16;
			for (int k=0; k<=i; k++) {
				best = min(best, dp[j.first][k]+abs(i-k-j.second));
			}
			dp[x][i] += best;
		}
	}
}
int main () {
	cin >> n >> m;
	int pi, wi;
	for (int i=2; i<=n+m; i++) {
		cin >> pi >> wi;
		adj[pi].push_back({i, wi});
	}
	dfs(1);
	long long o = 1e16;
	for (int i=0; i<=300; i++) {
		o = min(o, dp[1][i]);
	}
	cout << o << endl;
}

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