oj.uz

답안 #899519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899519 2024-01-06T11:16:12 Z LucaIlie Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 1 ms 2624 KB 
#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] );
    }
    for ( int x = n - 1; x > height[u]; x-- )
        dp[u][height[u]] = min( dp[u][height[u]], dp[u][x] - 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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2624 KB Output isn't correct
3 Halted 0 ms 0 KB -