Submission #500837

#TimeUsernameProblemLanguageResultExecution timeMemory
500837StickfishFireworks (APIO16_fireworks)C++17
7 / 100
5 ms7372 KiB
#include <iostream> #include <vector> using namespace std; using ll = long long; struct dpvl { ll l; ll r; ll mn; dpvl() {} dpvl(ll l_, ll r_, ll mn_): l(l_), r(r_), mn(mn_) {} ll operator()(ll x) { if (l <= x && x <= r) return mn; return min(abs(l - x), abs(r - x)) + mn; } }; const int MAXN = 300003; const ll INF = 1.77013e9; vector<pair<int, ll>> edg[MAXN]; pair<int, ll> root[MAXN]; ll lower_bound_dir(vector<dpvl>& v, ll x) { ll lb = -INF, ub = INF; while (ub - lb > 1) { ll mb = (lb + ub) / 2; ll ans = 0; for (auto d : v) { ans += d(mb + 1) - d(mb); } if (ans < x) lb = mb; else ub = mb; } return ub; } dpvl dfs(int v, int n) { if (v >= n) { return {root[v].second, root[v].second, 0}; } vector<dpvl> ch; for (auto [u, d] : edg[v]) { ch.push_back(dfs(u, n)); } ll l = lower_bound_dir(ch, 0); ll r = lower_bound_dir(ch, 1); ll mn = 0; for (auto d : ch) mn += d(l); return {l + root[v].second, r + root[v].second, mn}; } signed main() { int n, m; cin >> n >> m; ll addans = 0; for (int i = 1; i < n + m; ++i) { int u, d; cin >> u >> d; --u; if (u >= n) { addans += d; } else { edg[u].push_back({i, d}); root[i] = {u, d}; } } cout << dfs(0, n).mn << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...