제출 #262047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262047		define	Fireworks (APIO16_fireworks)	C++11	19 / 100	23 ms	1044 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N,M;
vector<P>G[305];
int dp[305][305];
void dfs(int x,int p){
	bool flag=false;
	for(auto i:G[x])if(i.first!=p){dfs(i.first,x);flag=1;}
	if(!flag){
		fill(dp[x]+1,dp[x]+301,inf);
	}
	rep(k,301){
		for(auto i:G[x])if(i.first!=p){
			int mn=inf;
			rep(j,k+1){
				chmin(mn,dp[i.first][j]+abs((k-j)-i.second));
			}
			dp[x][k]+=mn;
		}
	}
}
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>M;
	REP(i,N+M){
		int a,b;cin>>a>>b;a--;
		G[a].push_back({i,b});
	}
	dfs(0,0);
	int ans=inf;
	rep(i,301)chmin(ans,dp[0][i]);
	cout<<ans<<endl;
}

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