Submission #1024235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024235		vjudge1	Fireworks (APIO16_fireworks)	C++17	0 / 100	4 ms	604 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++) {
            ll minN = INF;
            for (ll j = 0; j <= 300; j++) {
                minN = min(minN, dp[v][j]+abs(j+w-i));
            }
            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 <= 30; i++) {
        cerr << dp[0][i] << ' ';
    }
    cerr << '\n';
    for (ll i = 0; i <= 300; i++) {
        ans = min(ans, dp[0][i]);
    }
    cout << ans << '\n';
    return 0;
}

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