oj.uz

Submission #930286

# Submission time Handle Problem Language Result Execution time Memory
930286 2024-02-19T09:16:28 Z boris_mihov Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 711 ms 221812 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 5000 + 10;
const int INF  = 2e9;

int n;
int h[MAXN];
int c[MAXN];
int perm[MAXN];
llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];
std::vector <int> g[MAXN];

llong f(int node, int value)
{
    // std::cout << "call: " << node << ' ' << value << '\n' << std::flush;
    if (bl[node][value])
    {
        return dp[node][value];
    }

    bl[node][value] = true;
    dp[node][value] = c[node];

    for (const int &u : g[node])
    {
        dp[node][value] += f(u, value);
    }

    if (h[node] >= value)
    {
        llong res = 0;
        for (const int &u : g[node])
        {
            res += f(u, h[node]);
        }

        dp[node][value] = std::min(dp[node][value], res);
    }

    return dp[node][value];
}

void solve()
{
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return h[x] < h[y];
    });

    int cnt = 0;
    int last = 0;

    for (int i = 1 ; i <= n ; ++i)
    {
        cnt += (h[perm[i]] > last);
        last = h[perm[i]];
        h[perm[i]] = cnt;
    }

    std::cout << f(1, 1) << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        int par;
        std::cin >> par >> h[i] >> c[i];
        if (i != 1) g[par].push_back(i);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 576 KB Output is correct
5 Correct 61 ms 221008 KB Output is correct
6 Correct 36 ms 216400 KB Output is correct
7 Correct 34 ms 215884 KB Output is correct
8 Correct 38 ms 220864 KB Output is correct
9 Correct 35 ms 216144 KB Output is correct
10 Correct 34 ms 215872 KB Output is correct
11 Correct 34 ms 215768 KB Output is correct
12 Correct 711 ms 221812 KB Output is correct
13 Correct 36 ms 216404 KB Output is correct
14 Correct 333 ms 221436 KB Output is correct
15 Correct 41 ms 216660 KB Output is correct
16 Correct 38 ms 221056 KB Output is correct
17 Correct 36 ms 216144 KB Output is correct
18 Correct 34 ms 215892 KB Output is correct
19 Correct 375 ms 221516 KB Output is correct
20 Correct 44 ms 216416 KB Output is correct
21 Correct 36 ms 215888 KB Output is correct
22 Correct 36 ms 220324 KB Output is correct
23 Correct 33 ms 216156 KB Output is correct
24 Correct 618 ms 221588 KB Output is correct
25 Correct 43 ms 216656 KB Output is correct
26 Correct 280 ms 221264 KB Output is correct
27 Correct 182 ms 220084 KB Output is correct
28 Correct 311 ms 220748 KB Output is correct
29 Correct 427 ms 220916 KB Output is correct
30 Correct 256 ms 220944 KB Output is correct
31 Correct 273 ms 221372 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 576 KB Output is correct
5 Correct 61 ms 221008 KB Output is correct
6 Correct 36 ms 216400 KB Output is correct
7 Correct 34 ms 215884 KB Output is correct
8 Correct 38 ms 220864 KB Output is correct
9 Correct 35 ms 216144 KB Output is correct
10 Correct 34 ms 215872 KB Output is correct
11 Correct 34 ms 215768 KB Output is correct
12 Correct 711 ms 221812 KB Output is correct
13 Correct 36 ms 216404 KB Output is correct
14 Correct 333 ms 221436 KB Output is correct
15 Correct 41 ms 216660 KB Output is correct
16 Correct 38 ms 221056 KB Output is correct
17 Correct 36 ms 216144 KB Output is correct
18 Correct 34 ms 215892 KB Output is correct
19 Correct 375 ms 221516 KB Output is correct
20 Correct 44 ms 216416 KB Output is correct
21 Correct 36 ms 215888 KB Output is correct
22 Correct 36 ms 220324 KB Output is correct
23 Correct 33 ms 216156 KB Output is correct
24 Correct 618 ms 221588 KB Output is correct
25 Correct 43 ms 216656 KB Output is correct
26 Correct 280 ms 221264 KB Output is correct
27 Correct 182 ms 220084 KB Output is correct
28 Correct 311 ms 220748 KB Output is correct
29 Correct 427 ms 220916 KB Output is correct
30 Correct 256 ms 220944 KB Output is correct
31 Correct 273 ms 221372 KB Output is correct
32 Correct 38 ms 221012 KB Output is correct
33 Runtime error 7 ms 1372 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 576 KB Output is correct
5 Correct 61 ms 221008 KB Output is correct
6 Correct 36 ms 216400 KB Output is correct
7 Correct 34 ms 215884 KB Output is correct
8 Correct 38 ms 220864 KB Output is correct
9 Correct 35 ms 216144 KB Output is correct
10 Correct 34 ms 215872 KB Output is correct
11 Correct 34 ms 215768 KB Output is correct
12 Correct 711 ms 221812 KB Output is correct
13 Correct 36 ms 216404 KB Output is correct
14 Correct 333 ms 221436 KB Output is correct
15 Correct 41 ms 216660 KB Output is correct
16 Correct 38 ms 221056 KB Output is correct
17 Correct 36 ms 216144 KB Output is correct
18 Correct 34 ms 215892 KB Output is correct
19 Correct 375 ms 221516 KB Output is correct
20 Correct 44 ms 216416 KB Output is correct
21 Correct 36 ms 215888 KB Output is correct
22 Correct 36 ms 220324 KB Output is correct
23 Correct 33 ms 216156 KB Output is correct
24 Correct 618 ms 221588 KB Output is correct
25 Correct 43 ms 216656 KB Output is correct
26 Correct 280 ms 221264 KB Output is correct
27 Correct 182 ms 220084 KB Output is correct
28 Correct 311 ms 220748 KB Output is correct
29 Correct 427 ms 220916 KB Output is correct
30 Correct 256 ms 220944 KB Output is correct
31 Correct 273 ms 221372 KB Output is correct
32 Correct 38 ms 221012 KB Output is correct
33 Runtime error 7 ms 1372 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -