Submission #609644

#	Time	Username	Problem	Language	Result	Execution time	Memory
609644		AugustinasJucas	Fireworks (APIO16_fireworks)	C++14	0 / 100	4 ms	7252 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;
const int dydis = 3e5 + 10;
const long long inf = 1e15;
int n, m, k;
const int MX = 300;
vector<pair<int, int> > gr[dydis];

long long dp[dydis][MX+1] = {};
long long st[dydis] = {};
void dfs(int v) {
    if(gr[v].size() == 0) {
        for(auto &x : dp[v]) x = inf;
        dp[v][0] = 0;
        return ;
    }

    for(auto x : gr[v]) {
        dfs(x.first);
    }

    for(auto x : gr[v]) {
        int u = x.first; long long w = x.second;

        for(int i = 0; i <= MX; i++) st[i] = inf;


        for(int i = 0; i <= MX; i++) {
            for(int j = 0; i+j <= MX; j++) {
                st[i+j] = min(st[i+j], abs(i-w) + dp[u][j]);
            }
        }

        for(int i = 0; i <= MX; i++) {
            dp[v][i] += st[i];
        }
    }
    //cout << "dp[" << v+1 << "]:\n";
   // for(int i = 0; i <= MX; i++) {
   //     cout << i << ": " << dp[v][i] << endl;
   // }
}

int main() {
    ifstream in("in.txt");
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    in >> m >> k;
    n = m + k;
    for(int i = 1; i < n; i++) {
        int p, w;
        in >> p >> w; p--;
        gr[p].push_back({i, w});
        //gr[i].push_back({p, w});
    }

    dfs(0);

    long long ans = inf;
    for(int i = 0; i <= MX; i++) {
        ans = min(ans, dp[0][i]);
    }

    cout << ans;
    return 0;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

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