Submission #227231

#	Time	Username	Problem	Language	Result	Execution time	Memory
227231		theStaticMind	Fireworks (APIO16_fireworks)	C++14	19 / 100	38 ms	8184 KiB

fireworks

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int n, m;
vector<ii> adj[300005];
int g[300005][305];

void dfs(int x, int c, int d){
	for(int i = 1; i <= 300; i++) g[x][i] = 0;
	if(x > n)
	for(int i = 1; i <= 300; i++){
		if(i == d) g[x][i] = 0;
		else g[x][i] = INF;
	}
	for(auto p : adj[x]){
		dfs(p.first, p.second, d + p.second);
		for(int a = 1; a <= 300; a++){
			g[x][a] += g[p.first][a];
		}
	}
	vector<int> f(305, INF);
	for(int j = 1; j <= 300; j++){
		for(int k = 1; k <= j + c && k <= 300; k++){
			f[j] = min(f[j], g[x][k] + abs(k - j));
		}
	}

	for(int i = 1; i <= 300; i++) g[x][i] = f[i];

}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for(int i = 2; i <= n + m; i++){
		int x, c;
		cin >> x >> c;
		adj[x].pb({i, c});
	}

	dfs(1, 0, 0);

	int ans = INF;
	for(int i = 1; i <= 300; i++) ans = min(ans, g[1][i]);

	cout << ans;

}

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