Submission #538625

#	Time	Username	Problem	Language	Result	Execution time	Memory
538625		Jarif_Rahman	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	330 ms	524288 KiB

worst_reporter2

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n;
vector<vector<int>> v;
vector<vector<ll>> dp;
vector<int> h;
vector<ll> cost;

void dfs(int nd){
    for(int x: v[nd]) dfs(x);
    for(int x: v[nd]) for(int i = 0; i < n; i++) dp[nd][i]+=dp[x][i];
    for(int i = h[nd]+1; i < n; i++){
        dp[nd][i]+=cost[nd];
    }
    for(int i = h[nd]-1; i >= 0; i--){
        dp[nd][i] = min(dp[nd][i+1], dp[nd][i]+cost[nd]);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    v.resize(n);
    dp.resize(n, vector<ll>(n, 0));
    h.resize(n);
    cost.resize(n);

    for(int i = 0; i < n; i++){
        int p; cin >> p >> h[i] >> cost[i];
        p--;
        if(p == i) continue;
        v[p].pb(i);
    }

    /*compress h*/{
        map<int, int> mp;
        vector<int> srt = h;
        sort(srt.begin(), srt.end());
        int in = 0;
        for(int i = 0; i < n; i++) mp[srt[i]] = in, in++;

        for(int &x: h) x = mp[x];
    }

    dfs(0);

    cout << *min_element(dp[0].begin(), dp[0].end()) << "\n";
}

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