Submission #40371

#	Time	Username	Problem	Language	Result	Execution time	Memory
40371		SpaimaCarpatilor	Fireworks (APIO16_fireworks)	C++14	0 / 100	385 ms	459384 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

int N, M, t[309], L[309];
long long maxH, dp[309][309*309], depth[309];
const long long INF = 1LL << 60;
vector < int > v[309];

int modul (int x)
{
    if (x < 0) return -x;
    return x;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=2; i<=N + M; i++)
    scanf ("%d %d", &t[i], &L[i]), v[t[i]].push_back (i), depth[i] = depth[t[i]] + L[i], maxH = max (maxH, depth[i]);
for (int nod = N + M; nod > N; nod --)
    for (int i=0; i<=maxH; i++)
        dp[nod][i] = modul (i - L[nod]);
for (int nod = N; nod>=1; nod--)
{
    ///adding
    for (auto son : v[nod])
        for (int i=0; i<=maxH; i++)
            dp[nod][i] += dp[son][i];
    ///shifting
    for (int i=maxH; i>=0; i--)
        for (int j=0; j<=i; j++)
            if (dp[nod][i - j] + modul (j - L[nod]) < dp[nod][i])
                dp[nod][i] = dp[nod][i - j] + modul (j - L[nod]);
    ///refreshing
/*    long long mini = INF;
    for (int i=0; i<=maxH; i++)
    {
        dp[nod][i] = min (mini + i, dp[nod][i]);
        if (dp[nod][i] - i < mini)
            mini = dp[nod][i] - i;
    }
    mini = INF;
    for (int i=maxH; i>=0; i--)
    {
        dp[nod][i] = min (mini - i, dp[nod][i]);
        if (dp[nod][i] + i < mini)
            mini = dp[nod][i] + i;
    }*/
}
long long ans = INF;
for (int i=0; i<=maxH; i++)
    if (dp[1][i] < ans)
        ans = dp[1][i];
printf ("%lld\n", ans);
return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:21:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
                        ^
fireworks.cpp:23:117: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &t[i], &L[i]), v[t[i]].push_back (i), depth[i] = depth[t[i]] + L[i], maxH = max (maxH, depth[i]);
                                                                                                                     ^

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