제출 #1293483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293483		kian2009	Fireworks (APIO16_fireworks)	C++20	19 / 100	11 ms	1188 KiB

fireworks

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

typedef long long ll;

const int MAXN = 3e2 + 10, INF = 1e9;

ll n, m, dp[MAXN][MAXN], sum[MAXN];
vector<pair<ll, ll>> adj[MAXN];

void input() {
	cin >> n >> m;
	for (int i = 1; i < n + m; i++) {
		ll u, w;
		cin >> u >> w;
		adj[--u].push_back({i, w});
	}
	for (int i = 0; i < n + m; i++)
		for (int j = 0; j < MAXN; j++)
			dp[i][j] = INF;
}

void dfs(int u) {
	if ((int)adj[u].size() == 0) {
		dp[u][0] = 0;
		return;
	}
	for (auto v : adj[u])
		dfs(v.first);
	for (int i = 0; i < MAXN; i++)
		sum[i] = 0;
	for (auto v : adj[u])
		for (int i = 0; i < MAXN; i++) {
			ll mi = INF;
			for (int j = 0; j <= i; j++)
				mi = min(mi, dp[v.first][j] + abs(v.second - (i - j)));
			sum[i] += mi;
		}
	for (int i = 0; i < MAXN; i++)
		dp[u][i] = min(dp[u][i], sum[i]);
}

ll findAns() {
	ll res = INF;
	for (int i = 0; i < MAXN; i++)
		res = min(res, dp[0][i]);
	return res;	
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	dfs(0);
	cout << findAns() << endl;
	return 0;
}

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