Submission #752966

#TimeUsernameProblemLanguageResultExecution timeMemory
752966benjaminkleynFireworks (APIO16_fireworks)C++17
7 / 100
5 ms7380 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 300010; int n, m; int p[2 * MAX]; ll c[2 * MAX]; vector<pair<int, ll>> g[MAX]; struct state { ll cost, dist, free_increase; }; state dp(int u) { if (u > n) return {0, 0, 0}; ll res = 0; vector<ll> T; ll min_val = 0; ll free_increase = LLONG_MAX; for (auto [v, l] : g[u]) { auto [t, d, free] = dp(v); res += t; T.push_back(l + d); free_increase = min(free_increase, free); min_val = max(min_val, d); } sort(T.begin(), T.end()); ll best = T[(T.size() - 1) / 2], free = T[T.size()/2] - T[(T.size()-1)/2]; if (min_val >= T[T.size()/2]) best = min_val, free = 0; else if (min_val >= best) best = min_val, free = T[T.size()/2] - min_val; for (ll x : T) res += abs(best - x); return {res - free_increase, best, free}; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; p[1] = -1, c[1] = 0; for (int i = 2; i <= n + m; i++) { cin >> p[i] >> c[i]; g[p[i]].push_back({i, c[i]}); } cout << dp(1).cost << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...