Submission #1024237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024237		vjudge1	Fireworks (APIO16_fireworks)	C++17	19 / 100	13 ms	1204 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 3E2+16, INF = ll(1E18)+16;
vii adj[MAXN];
ll dp[MAXN][MAXN];

void dfs (ll u) {
    if (adj[u].empty()) iota(dp[u], dp[u]+MAXN, 0);
    for (auto [v, w] : adj[u]) {
        dfs(v);
        for (ll i = 0; i <= 300; i++) { // wanted expl time
            ll minN = INF;
            for (ll mod = 0; mod <= i; mod++) { // mod on w
                minN = min(minN, dp[v][i-mod]+abs(mod-w));
            }
            dp[u][i] += minN;
        }
    }
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    for (ll v = 1; v < n+m; v++) {
        ll u, w;
        cin >> u >> w;
        u--;
        adj[u].push_back({ v, w });
    }
    dfs(0);
    ll ans = INF;
    for (ll i = 0; i <= 300; i++) {
        ans = min(ans, dp[0][i]);
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45