Submission #203930

#	Time	Username	Problem	Language	Result	Execution time	Memory
203930		Segtree	Fireworks (APIO16_fireworks)	C++14	19 / 100	24 ms	1144 KiB

fireworks

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 310
ll n,m;
vector<pair<ll,ll> > g[N];
ll dp[N][N];
void dfs(ll x){
	if(x>n){
		rep(i,N)dp[x][i]=1e9;
		dp[x][0]=0;
		return;
	}
	rep(i,N)dp[x][i]=0;
	for(auto e:g[x]){
		dfs(e.first);
		rep(i,N){
			ll mi=1e9;
			for(int j=0;j<=i;j++){
				chmin(mi,dp[e.first][j]+abs((i-j)-e.second));
			}
			dp[x][i]+=mi;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=2;i<=n+m;i++){
		ll p,c; cin>>p>>c;
		g[p].push_back(make_pair(i,c));
	}
	dfs(1);
	ll ans=1e17;
	rep(i,N){
		chmin(ans,dp[1][i]);
	}
	cout<<ans<<endl;
}

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