fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll INF = 1e18;
  6.  
  7. struct Line {
  8.     ll m, b;
  9.     int id; // Lưu chỉ số q để check cửa sổ trượt
  10.     ll eval(ll x) { return m * x + b; }
  11. };
  12.  
  13. // Kiểm tra đường l2 có vô dụng giữa l1 và l3 không
  14. bool is_bad(Line l1, Line l2, Line l3) {
  15.     // (b2-b1)/(m1-m2) >= (b3-b2)/(m2-m3)
  16.     return (__int128)(l2.b - l1.b) * (l2.m - l3.m) >= (__int128)(l3.b - l2.b) * (l1.m - l2.m);
  17. }
  18.  
  19. int n, s;
  20. struct Info { int Q, W; ll C; } a[5005];
  21. vector<int> adj[5005];
  22. int pre[5005], sz[5005], timer = 0;
  23. ll dp[5005][5005];
  24.  
  25. void dfs(int u, int p) {
  26.     pre[++timer] = u; sz[u] = 1;
  27.     for (int v : adj[u]) if (v != p) { dfs(v, u); sz[u] += sz[v]; }
  28. }
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(0); cin.tie(0);
  32.     cin >> n >> s;
  33.     for (int i = 1; i <= n; i++) cin >> a[i].Q >> a[i].W >> a[i].C;
  34.     for (int i = 1; i < n; i++) {
  35.         int u, v; cin >> u >> v;
  36.         adj[u].push_back(v); adj[v].push_back(u);
  37.     }
  38.     dfs(1, 0);
  39.  
  40.     for (int i = 1; i <= n + 1; i++) fill(dp[i], dp[i] + s + 1, INF);
  41.     dp[1][0] = 0;
  42.  
  43.     for (int i = 1; i <= n; i++) {
  44.         int u = pre[i];
  45.         int W = a[u].W, Q = a[u].Q; ll C = a[u].C;
  46.  
  47.         // Nhánh 1: Không chọn u (nhảy qua cây con)
  48.         int skip = i + sz[u];
  49.         for (int j = 0; j <= s; j++) dp[skip][j] = min(dp[skip][j], dp[i][j]);
  50.  
  51.         // Nhánh 2: Chọn u (CHT theo từng số dư r)
  52.         for (int r = 0; r < W; r++) {
  53.             deque<Line> dq;
  54.             for (int p = 0; p * W + r <= s; p++) {
  55.                 // 1. Thêm đường thẳng q = p-1 vào CHT (vì k >= 1)
  56.                 int q = p - 1;
  57.                 if (q >= 0 && dp[i][q * W + r] != INF) {
  58.                     Line cur = {-2LL * q * C, dp[i][q * W + r] + 1LL * q * q * C, q};
  59.                     while (dq.size() >= 2 && is_bad(dq[dq.size() - 2], dq.back(), cur)) dq.pop_back();
  60.                     dq.push_back(cur);
  61.                 }
  62.  
  63.                 // 2. Loại bỏ đường thẳng cũ (q < p - Q)
  64.                 while (!dq.empty() && dq.front().id < p - Q) dq.pop_front();
  65.  
  66.                 // 3. Truy vấn min tại x = p
  67.                 if (!dq.empty()) {
  68.                     while (dq.size() >= 2 && dq[0].eval(p) >= dq[1].eval(p)) dq.pop_front();
  69.                     dp[i + 1][p * W + r] = min(dp[i + 1][p * W + r], dq.front().eval(p) + 1LL * p * p * C);
  70.                 }
  71.             }
  72.         }
  73.     }
  74.  
  75.     if (dp[n + 1][s] >= INF) cout << -1;
  76.     else cout << dp[n + 1][s];
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5648KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OySLkn
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

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!