結果

問題 No.417 チューリップバブル
ユーザー CZS_AK_IOI2025
提出日時 2025-04-23 22:49:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 1,209 bytes
コンパイル時間 2,290 ms
コンパイル使用メモリ 197,620 KB
実行使用メモリ 87,908 KB
最終ジャッジ日時 2025-04-23 22:49:32
合計ジャッジ時間 5,002 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define maxn 205
using namespace std;
int n,m,dp[maxn][200001],U[maxn];
struct EDGE{int v,w;};
vector<EDGE>edge[maxn];
namespace CZS_Office{
	inline int read(){
		int x=0,f=1;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-')f=-1;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
		return x*f;
	}
	inline void write(int x){
		if(x<0){
			putchar('-');
			x=-x;
		}
		if(x>9)write(x/10);
		putchar(x%10+'0');
		return;
	}
}
using namespace CZS_Office;
int siz[maxn];
inline void dfs(int rt,int fa){
	for(EDGE E:edge[rt]){
		int v=E.v,w=E.w;
		if(v==fa)continue;
		dfs(v,rt);
		siz[rt]+=siz[v]+w;
		for(int i=siz[rt];i>=w;--i){
			dp[rt][i]=max(dp[rt][i],dp[v][i-w]+U[rt]);
			for(int j=i-w;j>=0;--j){
				dp[rt][i]=max(dp[rt][i],dp[rt][j]+dp[v][i-w-j]);
			}
		}
	}
	dp[rt][0]=U[rt];
	for(int i=1;i<=siz[rt];++i)dp[rt][i]=max(dp[rt][i],dp[rt][i-1]);
	return;
}
signed main(){
	n=read();m=read();m/=2;
	for(int i=0;i<n;++i)U[i]=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read(),w=read();
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dfs(0,-1);
	for(int i=0;i<=m;++i)dp[0][m]=max(dp[0][i],dp[0][m]);
	write(dp[0][m]);
	return 0;
}
0