Submission #959925

#	Time	Username	Problem	Language	Result	Execution time	Memory
959925		Trisanu_Das	Fireworks (APIO16_fireworks)	C++17	19 / 100	20 ms	1184 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300 + 10;
const ll inf = 1e18;
 
vector<pair<int,int>> t[maxn];
ll dp[maxn][maxn];
int lo[maxn], r[maxn];
 
void dfs(int v){
	if (t[v].empty()){
		dp[v][0] = 0;
		for (int j = 1; j < maxn; j++)
			dp[v][j] = inf;
		return;
	}
	for (auto [u,c] : t[v]){
		dfs(u);
		for (int i = 0; i < maxn; i++){
			ll now = inf;
			for (int j = 0; j <= i; j++)
				now = min(now, dp[u][j] + abs(i-j-c));
			dp[v][i] += now;
		}
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 2; i <= n+m; i++){
		int v, c;
		cin >> v >> c;
		t[v].push_back({i,c});
	}
	dfs(1);
	ll answer = inf;
	for (int i = 0; i < maxn; i++)
		answer = min(answer, dp[1][i]);
	cout << answer << endl;
}

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