제출 #40370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40370		SpaimaCarpatilor	Fireworks (APIO16_fireworks)	C++14	0 / 100	2090 ms	524288 KiB

fireworks

#include<bits/stdc++.h>

using namespace std;

int N, M, t[309], L[309];
long long maxH, dp[309][2 * 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=-maxH; i<=maxH; i++)
        dp[nod][i + maxH] = modul (i - L[nod]);
for (int nod = N; nod>=1; nod--)
{
    ///adding
    for (auto son : v[nod])
        for (int i=0; i<=2 * maxH; i++)
            dp[nod][i] += dp[son][i];
    ///shifting
    for (int i=2 * maxH; i>=0; i--)
        if (i >= L[nod]) dp[nod][i] = dp[nod][i - L[nod]];
        else dp[nod][i] = INF;
    ///refreshing
    long long mini = INF;
    for (int i=0; i<=2 * 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=2 * 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<=2 * maxH; i++)
    if (dp[1][i] < ans)
        ans = dp[1][i];
printf ("%lld\n", ans);
return 0;
}

컴파일 시 표준 에러 (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