oj.uz

Submission #40371

# Submission time Handle Problem Language Result Execution time Memory
40371 2018-01-31T12:34:41 Z SpaimaCarpatilor Fireworks (APIO16_fireworks) C++14
0 / 100
 385 ms 459384 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 459384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 459384 KB Output is correct
2 Incorrect 3 ms 459384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 459384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 459384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -