Submission #1153055

#TimeUsernameProblemLanguageResultExecution timeMemory
1153055vladiliusFireworks (APIO16_fireworks)C++20
19 / 100
134 ms3276 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; int f = n + m; vector<ll> p(f + 1); vector<pii> g[f + 1]; for (int i = 2; i <= f; i++){ int x, w; cin>>x>>w; g[x].pb({i, w}); p[i] = p[x] + w; } const int A = 1e3; vector<vector<ll>> t(f + 1, vector<ll>(A + 1)); for (int i = n + 1; i <= f; i++){ for (int j = 0; j <= A; j++){ t[i][j] = abs(j - p[i]); } } function<void(int)> fill = [&](int v){ if (v > n) return; for (auto [i, w]: g[v]){ fill(i); } for (int x = 0; x <= A; x++){ for (auto [i, w]: g[v]){ ll mn = 1e18; for (int a = 0; a <= min(A, w + x); a++){ mn = min(mn, t[i][a] + abs(a - x)); } t[v][x] += mn; } } }; fill(1); ll out = 1e18; for (int x = 0; x <= A; x++){ out = min(out, t[1][x]); } cout<<out<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...