結果

問題 No.417 チューリップバブル
ユーザー vjudge1
提出日時 2025-04-22 16:42:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 630 bytes
コンパイル時間 2,128 ms
コンパイル使用メモリ 196,460 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-04-22 16:42:55
合計ジャッジ時間 8,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int N=2005; 
int m[N][N],a[N],f[N][N],n,t; 
vector<int> g[N];
void dfs(int u,int fa){
		for (auto v:g[u]){
			if (v==fa) continue;
			for(int i=m[u][v]*2;i<=t;i++)f[v][i]+=a[v];
			dfs(v,u);
			for (int j=t;j>=2*m[u][v];j--){ 
				for (int k=0;k<=j-m[u][v]*2;k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
			}
		} 
}
signed main ()
{
	cin>>n>>t;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	int u,v,w;
	for (int i=1;i<=n-1;i++){
		cin>>u>>v>>w;
		u++;
		v++;
		m[u][v]=w;
		m[v][u]=w;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0); 
	cout<<f[1][t]+a[1]<<endl;
	return 0;
}
0