Submission #3025245
Source Code Expand
#ifndef BZ #pragma GCC optimize "-O3" #endif #include <bits/stdc++.h> #define FASTIO #define ALL(v) (v).begin(), (v).end() #define rep(i, l, r) for (int i = (l); i < (r); ++i) #ifdef FASTIO #define scanf abacaba #define printf abacaba #endif typedef long long ll; typedef long double ld; typedef unsigned long long ull; using namespace std; /* ll pw(ll a, ll b) { ll ans = 1; while (b) { while (!(b & 1)) b >>= 1, a = (a * a) % MOD; ans = (ans * a) % MOD, --b; } return ans; } */ const int MAXN = 55; int n; ll x, d; ll m[MAXN]; int p[MAXN]; int sz[MAXN]; const int MX = 3500000; array<ll, MX> dp; int lst[MAXN]; int main() { #ifdef FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); #endif cin >> n >> x >> d; cin >> m[0]; for (int i = 1; i < n; ++i) { cin >> m[i] >> p[i]; --p[i]; } for (int i = n - 1; i >= 0; --i) { sz[i] += 1; m[p[i]] += m[i]; sz[p[i]] += sz[i]; } vector<array<ll, 3>> vv; vv.push_back({m[0], sz[0], x}); for (int i = 1; i < n; ++i) vv.push_back({m[i], sz[i], d}); sort(vv.begin(), vv.end(), [] (array<ll, 3> a, array<ll, 3> b) { return a[0] * b[1] < a[1] * b[0]; }); ll add = 0; for (int i = 0; i < vv.size(); ++i) { if (vv[i][2] <= n) continue; ll lf = x; for (int j = 0; j < i; ++j) { lf -= vv[j][0] * vv[j][2]; if (lf < 0) break; } for (int j = i + 1; j < vv.size() && lf >= 0; ++j) { int k = 0; while ((k + 1) * vv[j][0] / vv[i][0] * vv[i][1] < (k + 1) * vv[j][1]) ++k; lf -= vv[j][0] * k; } if (lf >= 0) { ll go = min(vv[i][2] - n, lf / vv[i][0]); add += vv[i][1] * go; x -= vv[i][0] * go; lf -= vv[i][0] * go; vv[i][2] -= go; if (vv[i][2] > n) break; } else { break; } } dp.fill(x + 1); dp[0] = 0; for (int i = 0; i < vv.size(); ++i) { int n = vv[i][1]; ll cs = vv[i][0]; ll av = vv[i][2]; for (int j = 0; j < n; ++j) lst[j] = j; auto dp2 = dp; for (int i = 0; i < MX; ++i) { int g = i % n; if (lst[g] <= i) lst[g] = i + n; int k = (lst[g] - i) / n; for (; lst[g] < MX && k <= av; lst[g] += n, ++k) { if (dp2[lst[g]] > dp[i] + cs * k) dp2[lst[g]] = dp[i] + cs * k; else break; } } dp = dp2; } ll ans = add; for (int i = 0; i < MX; ++i) if (dp[i] <= x) ans = max(ans, add + i); cout << ans << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Sweet Alchemy |
User | LHiC |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2471 Byte |
Status | WA |
Exec Time | 1753 ms |
Memory | 55040 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 900 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56, b57, b58, b59, b60, b61, b62, b63 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 118 ms | 54912 KB |
a02 | AC | 118 ms | 54912 KB |
a03 | AC | 186 ms | 54912 KB |
b04 | AC | 83 ms | 54912 KB |
b05 | AC | 1723 ms | 54912 KB |
b06 | WA | 1677 ms | 54912 KB |
b07 | AC | 1677 ms | 54912 KB |
b08 | AC | 1745 ms | 54912 KB |
b09 | AC | 1728 ms | 54912 KB |
b10 | AC | 1724 ms | 54912 KB |
b11 | AC | 1723 ms | 54912 KB |
b12 | AC | 1727 ms | 54912 KB |
b13 | AC | 1723 ms | 54912 KB |
b14 | AC | 187 ms | 54912 KB |
b15 | AC | 153 ms | 54912 KB |
b16 | AC | 1660 ms | 54912 KB |
b17 | AC | 291 ms | 54912 KB |
b18 | AC | 458 ms | 54912 KB |
b19 | AC | 118 ms | 54912 KB |
b20 | AC | 735 ms | 54912 KB |
b21 | AC | 1699 ms | 54912 KB |
b22 | AC | 1181 ms | 54912 KB |
b23 | AC | 84 ms | 54912 KB |
b24 | AC | 1737 ms | 54912 KB |
b25 | AC | 1725 ms | 54912 KB |
b26 | AC | 1730 ms | 54912 KB |
b27 | AC | 1747 ms | 54912 KB |
b28 | AC | 1734 ms | 54912 KB |
b29 | AC | 1730 ms | 54912 KB |
b30 | AC | 1728 ms | 54912 KB |
b31 | AC | 1728 ms | 54912 KB |
b32 | AC | 1739 ms | 54912 KB |
b33 | AC | 1726 ms | 54912 KB |
b34 | AC | 1696 ms | 54912 KB |
b35 | AC | 119 ms | 54912 KB |
b36 | AC | 186 ms | 54912 KB |
b37 | AC | 222 ms | 54912 KB |
b38 | AC | 460 ms | 54912 KB |
b39 | AC | 739 ms | 54912 KB |
b40 | AC | 1662 ms | 54912 KB |
b41 | AC | 289 ms | 54912 KB |
b42 | AC | 1175 ms | 54912 KB |
b43 | AC | 152 ms | 54912 KB |
b44 | WA | 1753 ms | 54912 KB |
b45 | AC | 1736 ms | 54912 KB |
b46 | AC | 1745 ms | 54912 KB |
b47 | AC | 1732 ms | 54912 KB |
b48 | WA | 1735 ms | 54912 KB |
b49 | WA | 1748 ms | 54912 KB |
b50 | AC | 1720 ms | 54912 KB |
b51 | AC | 1738 ms | 54912 KB |
b52 | WA | 1733 ms | 55040 KB |
b53 | WA | 1736 ms | 54912 KB |
b54 | AC | 839 ms | 55040 KB |
b55 | WA | 1211 ms | 54912 KB |
b56 | WA | 1713 ms | 54912 KB |
b57 | AC | 1727 ms | 54912 KB |
b58 | AC | 1729 ms | 54912 KB |
b59 | AC | 1726 ms | 55040 KB |
b60 | AC | 1734 ms | 54912 KB |
b61 | AC | 1725 ms | 54912 KB |
b62 | WA | 1747 ms | 55040 KB |
b63 | AC | 1732 ms | 54912 KB |