結果
問題 | No.417 チューリップバブル |
ユーザー |
![]() |
提出日時 | 2021-05-29 15:06:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 360 ms / 2,000 ms |
コード長 | 2,028 bytes |
コンパイル時間 | 2,300 ms |
コンパイル使用メモリ | 205,860 KB |
最終ジャッジ日時 | 2025-01-21 20:29:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) template<typename T> void chmax(T& reference, T value) { reference = max(reference, value); } template<typename T> void chmaxmap(map<T, T>& m, T key, T value) { if (m.count(key)) { chmax(m[key], value); } else { m[key] = value; } } template<typename T> void chmin(T& reference, T value) { reference = min(reference, value); } int main() { int n, m; cin >> n >> m; vector<ll> us(n); rep(i, n) cin >> us[i]; vector<vector<P>> g(n); rep(i, n - 1) { ll a, b, c; cin >> a >> b >> c; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector<vector<ll>> dp(n, vector<ll>(m + 1, -1)); //dp[i][j]...iの村でm時間消費して得られる税収の最大値 function<void(int, int)> dfs = [&](int current, int parent) { dp[current][0] = 0; for (auto nx : g[current]) { if (nx.first == parent) continue; dfs(nx.first, current); ll time = nx.second * 2; for (int ij = m - time; ij >= 0; ij--) { for (int j = 0; j <= ij; j++) { int i = ij - j; if (dp[nx.first][j] == -1) continue; if (dp[current][i] == -1) continue; ll cost = dp[current][i] + dp[nx.first][j]; chmax(dp[current][ij + time], cost); } } } for (int i = 0; i <= m; i++) { if (dp[current][i] == -1) continue; dp[current][i] += us[current]; } }; dfs(0, -1); ll ans = 0; rep(i, m + 1) { chmax(ans, dp[0][i]); } cout << ans << endl; return 0; }