제출 #899309

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

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5000;
const long long INF = 1e15;
int n;
int parent[MAX_N + 1], height[MAX_N + 1], cost[MAX_N + 1];
long long dp[MAX_N + 1][MAX_N + 1];
vector<int> children[MAX_N + 1];
map<int, int> mp;

void dfs( int u ) {
    for ( int v: children[u] )
        dfs( v );

    dp[u][n] = INF;
    for ( int x = n - 1; x >= 0; x-- ) {
        for ( int v: children[u] )
            dp[u][x] += dp[v][x];
        //dp[u][x] = min( dp[u][x], dp[u][x + 1] );
    }
    long long c = dp[u][height[u]];
    for ( int x = height[u]; x >= 0; x-- )
        dp[u][x] = min( dp[u][x], c - cost[u] );
}

int main() {
    long long c = 0;

    cin >> n;
    for ( int v = 1; v <= n; v++ )
        cin >> parent[v] >> height[v] >> cost[v];

    for ( int v = 2; v <= n; v++ )
        children[parent[v]].push_back( v );

    for ( int v = 1; v <= n; v++ )
        mp[height[v]] = 1, c += cost[v];
    int val = 0;
    for ( auto p: mp )
        mp[p.first] = val++;
    for ( int v = 1; v <= n; v++ )
        height[v] = mp[height[v]];

    dfs( 1 );

    cout << c + dp[1][0] << "\n";

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21