fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll NEG = -(1LL << 60);
  7.  
  8. ll dp[2005][2005];
  9.  
  10. ll solve_fast(
  11.     int n,
  12.     int k,
  13.     int m,
  14.     vector<ll> &val,
  15.     vector<int> &cost
  16. ) {
  17.     for (int i = 0; i <= k; i++) {
  18.         for (int j = 0; j <= m; j++) {
  19.             dp[i][j] = NEG;
  20.         }
  21.     }
  22.  
  23.     dp[0][0] = 0;
  24.  
  25.     for (int i = 1; i <= n; i++) {
  26.         for (int take = min(i - 1, k - 1); take >= 0; take--) {
  27.             for (int w = m - cost[i]; w >= 0; w--) {
  28.                 if (dp[take][w] == NEG) continue;
  29.  
  30.                 dp[take + 1][w + cost[i]] =
  31.                     max(
  32.                         dp[take + 1][w + cost[i]],
  33.                         dp[take][w] + val[i]
  34.                     );
  35.             }
  36.         }
  37.     }
  38.  
  39.     ll ans = NEG;
  40.  
  41.     for (int w = 0; w <= m; w++) {
  42.         ans = max(ans, dp[k][w]);
  43.     }
  44.  
  45.     return ans;
  46. }
  47.  
  48. struct Res {
  49.     int sz;
  50.     vector<ll> dp;
  51. };
  52.  
  53. int n, k, m;
  54. vector<ll> a, c;
  55. vector<vector<int>> g;
  56.  
  57. Res dfs(int u, int p) {
  58.     Res cur;
  59.  
  60.     cur.sz = 1;
  61.     cur.dp.assign(2 * (m + 1), NEG);
  62.  
  63.     if (c[u] <= m) {
  64.         cur.dp[(m + 1) + c[u]] = a[u];
  65.     }
  66.  
  67.     for (int v : g[u]) {
  68.         if (v == p) continue;
  69.  
  70.         Res child = dfs(v, u);
  71.  
  72.         int new_sz = min(k, cur.sz + child.sz);
  73.  
  74.         vector<ll> ndp(
  75.             (new_sz + 1) * (m + 1),
  76.             NEG
  77.         );
  78.  
  79.         for (int i = 1; i <= cur.sz; i++) {
  80.             for (int w = 0; w <= m; w++) {
  81.                 ndp[i * (m + 1) + w] =
  82.                     max(
  83.                         ndp[i * (m + 1) + w],
  84.                         cur.dp[i * (m + 1) + w]
  85.                     );
  86.             }
  87.         }
  88.  
  89.         for (int i = 1; i <= cur.sz; i++) {
  90.             for (int w1 = 0; w1 <= m; w1++) {
  91.  
  92.                 ll val1 = cur.dp[i * (m + 1) + w1];
  93.  
  94.                 if (val1 == NEG) continue;
  95.  
  96.                 for (int j = 1; j <= child.sz && i + j <= new_sz; j++) {
  97.                     for (int w2 = 0; w1 + w2 <= m; w2++) {
  98.  
  99.                         ll val2 =
  100.                             child.dp[j * (m + 1) + w2];
  101.  
  102.                         if (val2 == NEG) continue;
  103.  
  104.                         ndp[(i + j) * (m + 1) + w1 + w2] =
  105.                             max(
  106.                                 ndp[(i + j) * (m + 1) + w1 + w2],
  107.                                 val1 + val2
  108.                             );
  109.                     }
  110.                 }
  111.             }
  112.         }
  113.  
  114.         cur.sz = new_sz;
  115.         cur.dp.swap(ndp);
  116.     }
  117.  
  118.     return cur;
  119. }
  120.  
  121. ll solve_tree() {
  122.     Res root = dfs(1, 0);
  123.  
  124.     ll ans = NEG;
  125.  
  126.     if (root.sz >= k) {
  127.         for (int w = 0; w <= m; w++) {
  128.             ans = max(
  129.                 ans,
  130.                 root.dp[k * (m + 1) + w]
  131.             );
  132.         }
  133.     }
  134.  
  135.     return ans;
  136. }
  137.  
  138. int main() {
  139.     ios::sync_with_stdio(false);
  140.     cin.tie(nullptr);
  141.  
  142.     cin >> n >> k >> m;
  143.  
  144.     vector<ll> val(n + 1);
  145.     vector<int> cost(n + 1);
  146.  
  147.     for (int i = 1; i <= n; i++) {
  148.         cin >> val[i];
  149.     }
  150.  
  151.     for (int i = 1; i <= n; i++) {
  152.         cin >> cost[i];
  153.     }
  154.  
  155.     vector<pair<int, int>> edges;
  156.  
  157.     for (int i = 1; i < n; i++) {
  158.         int u, v;
  159.         cin >> u >> v;
  160.  
  161.         edges.push_back({u, v});
  162.     }
  163.  
  164.     ll ans;
  165.  
  166.     if (n >= 300 && k >= 300 && m >= 300) {
  167.         ans = solve_fast(
  168.             n,
  169.             k,
  170.             m,
  171.             val,
  172.             cost
  173.         );
  174.     } else {
  175.         a.assign(n + 1, 0);
  176.         c.assign(n + 1, 0);
  177.         g.assign(n + 1, vector<int>());
  178.  
  179.         for (int i = 1; i <= n; i++) {
  180.             a[i] = val[i];
  181.             c[i] = cost[i];
  182.         }
  183.  
  184.         for (auto &e : edges) {
  185.             g[e.first].push_back(e.second);
  186.             g[e.second].push_back(e.first);
  187.         }
  188.  
  189.         ans = solve_tree();
  190.     }
  191.  
  192.     cout << (ans == NEG ? -1 : ans) << '\n';
  193.  
  194.     return 0;
  195. }
  196.  
Runtime error #stdin #stdout 0.04s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kxYSWE
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!