結果
問題 | No.417 チューリップバブル |
ユーザー |
![]() |
提出日時 | 2016-08-26 22:39:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,317 ms / 2,000 ms |
コード長 | 861 bytes |
コンパイル時間 | 1,384 ms |
コンパイル使用メモリ | 163,548 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 09:35:05 |
合計ジャッジ時間 | 16,967 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long struct edge { int to, cost; }; int N, M, U[200]; vector< edge > g[200]; vector< int > rec(int idx, int par = -1) { vector< int > dp(M + 1, 0); dp[0] = U[idx]; for(auto e : g[idx]) { if(par == e.to) continue; vector< int > pp = rec(e.to, idx); for(int j = M; j >= 0; j--) { for(int k = M; k >= 0; k--) { int next = k + j + e.cost * 2; if(next > M) continue; dp[next] = max(dp[next], dp[j] + pp[k]); } } } return (dp); } signed main() { cin >> N >> M; for(int i = 0; i < N; i++) { cin >> U[i]; } for(int i = 0; i < N - 1; i++) { int A, B, C; cin >> A >> B >> C; g[A].push_back((edge) {B, C}); g[B].push_back((edge) {A, C}); } auto p = rec(0); cout << *max_element(begin(p), end(p)) << endl; }