Submission #239286

#	Time	Username	Problem	Language	Result	Execution time	Memory
239286		jjaewon	Fireworks (APIO16_fireworks)	C++14	19 / 100	27 ms	8320 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int N,M,P[300010];
ll C[300010],dp[333][333];
vector<pair<int,ll>> ch[300010];

void dfs(int now){
	if(now>N){
		dp[now][0]=0;
		return;
	}
	for(auto i:ch[now])	dfs(i.fi);
	for(int i=0;i<=300;i++){
		dp[now][i]=0;
		for(auto j:ch[now]){
			ll curr=inf;
			for(int k=0;k<=i;k++){
				curr=min(curr,dp[j.fi][k]+abs(j.se-i+k));
			}
			dp[now][i]+=curr;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>M;
	for(int i=2;i<=N+M;i++){
		cin>>P[i]>>C[i];
		ch[P[i]].push_back({i,C[i]});
	}
	memset(dp,inf,sizeof(dp));
	dfs(1);
	ll ans=inf;
	for(int i=0;i<=300;i++) ans=min(ans,dp[1][i]);
	cout<<ans;
	return 0;
}

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