Submission #543062

#	Time	Username	Problem	Language	Result	Execution time	Memory
543062		amunduzbaev	Fireworks (APIO16_fireworks)	C++17	26 / 100	26 ms	1144 KiB

fireworks

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

#define ar array
#define int long long
const int N = 305;
const int inf = 1e18;
vector<ar<int, 2>> edges[N];
int dp[N][N];

void dfs(int u){
	for(auto x : edges[u]){
		dfs(x[0]);
		for(int j=0;j<N;j++){
			int pre = dp[u][j]; dp[u][j] = inf;
			for(int l=0;l<=j;l++){
				dp[u][j] = min(dp[u][j], pre + dp[x[0]][l] + abs(j - l - x[1]));
			}
		}
	}
	
	if(edges[u].empty()){
		memset(dp[u], 63, sizeof dp[u]);
		dp[u][0] = 0;
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 

	int n, m; cin>>n>>m;
	for(int i=1;i<n+m;i++){
		int p, c; cin>>p>>c;
		edges[--p].push_back({i, c});
	}
	
	if(n == 1){
		sort(edges[0].begin(), edges[0].end(), [&](auto& a, auto& b){
			return a[1] < b[1];
		});
		
		int C = edges[0][m / 2][1];
		long long res = 0;
		for(auto x : edges[0]) res += abs(C - x[1]);
		cout<<res<<"\n";
		return 0;
	}
	
	dfs(0);
	int i = 1;
	while(i < N && dp[0][i] <= dp[0][i-1]) i++;
	cout<<dp[0][i-1]<<"\n";
	while(i < N && dp[0][i] > dp[0][i-1]) i++;
	assert(i == N);
}

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