Submission #1175917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175917		andrei_iorgulescu	Fireworks (APIO16_fireworks)	C++20	0 / 100	3 ms	7568 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 - c[nod]);
    }
    else
    {
        /*for (int i = 0; i <= 300; i++)
        {
            dp[nod][i] = inf;
            for (int j = 0; j <= i; j++)
            {
                int ct = abs(j - c[nod]);
                for (auto fiu : f[nod])
                    ct += dp[fiu][i - j];
                dp[nod][i] = min(dp[nod][i], ct);
            }
        }*/
        for (int i = 0; i <= 300; i++)
            dp[nod][i] = inf;
        for (int i = c[nod]; i <= 300; i++)
        {
            int ct = 0;
            for (auto fiu : f[nod])
                ct += dp[fiu][i - c[nod]];
            dp[nod][i] = ct;
        }
        for (int i = 1; i <= 300; i++)
            dp[nod][i] = min(dp[nod][i], dp[nod][i - 1] + 1);
        /*for (int itr = 1; itr <= 300; itr++)
        {
            for (int i = 300; i >= 1; i--)
                dp[nod][i] = min(dp[nod][i], dp[nod][i - 1] + 1);
        }*/
        /*for (int itr = 1; itr <= c[nod]; itr++)
        {
            for (int i = 0; i < 300; i++)
                dp[nod][i] = min(dp[nod][i], dp[nod][i + 1] + 1);
        }*/
        for (int i = 299; i >= 0; i--)
            dp[nod][i] = min(dp[nod][i], dp[nod][i + 1] + 1);
    }
}

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