結果
問題 | No.417 チューリップバブル |
ユーザー |
|
提出日時 | 2023-01-31 14:12:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 960 ms / 2,000 ms |
コード長 | 539 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 77,376 KB |
最終ジャッジ日時 | 2024-06-30 17:31:02 |
合計ジャッジ時間 | 12,639 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
N, M = map(int, input().split())M //= 2U = [int(input()) for _ in range(N)]G = [[] for _ in range(N)]for _ in range(N-1):A,B,C = map(int, input().split())G[A].append((B, C))G[B].append((A, C))dp = [[U[i]]*(M+1) for i in range(N)]def dfs(x, par=-1):for nx, t in G[x]:if nx==par:continuedfs(nx, x)for m in range(M+1)[::-1]:for mm in range(M-m+1-t):T = m+mm+tdp[x][T] = max(dp[x][T], dp[x][m]+dp[nx][mm])dfs(0)print(max(dp[0]))