Submission #1175908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175908		andrei_iorgulescu	Fireworks (APIO16_fireworks)	C++20	0 / 100	7 ms	7492 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n, m;
int t[300005], c[300005];
vector<int> f[300005];
int h[300005];
int dp[305][305];

void root(int nod)
{
    for (auto fiu : f[nod])
    {
        h[fiu] = c[fiu] + h[nod];
        root(fiu);
    }
}

void calc(int nod)
{
    for (auto fiu : f[nod])
        calc(fiu);
    if (f[nod].empty())
    {
        for (int i = 0; i <= 300; i++)
            dp[nod][i] = abs(i - h[nod]);
    }
    else
    {
        for (int i = 0; i <= 300; i++)
        {
            int ct = 0;
            for (int j = 0; j < f[nod].size(); j++)
            {
                int mnm = inf;
                int fiu = f[nod][j];
                for (int q = 0; q <= 300; q++)
                    mnm = min(mnm, abs(i - q) + dp[fiu][q]);
                ct += mnm;
            }
            dp[nod][i] = ct;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    n += m;
    for (int i = 2; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        f[t[i]].push_back(i);
    }
    root(1);
    calc(1);
    int mnm = inf;
    for (auto i = 0; i <= 300; i++)
        mnm = min(mnm, dp[1][i]);
    cout << mnm;
    return 0;
}

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