제출 #930286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930286		boris_mihov	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	711 ms	221812 KiB

worst_reporter2

#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 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21