Submission #475419

#	Time	Username	Problem	Language	Result	Execution time	Memory
475419		nafis_shifat	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	481 ms	392868 KiB

worst_reporter2

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e3+5;
const int inf=1e9;


ll c[mxn];
int h[mxn];
vector<int> adj[mxn];

ll dp[mxn][mxn];
ll suf[mxn][mxn];

int n;

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

    for(int i = 1; i <= n; i++) {
        dp[u][i] = c[u];
        if(i == h[u]) dp[u][i] = 0;
        for(int v : adj[u]) {
            dp[u][i] += suf[v][i];
        }
    }

    suf[u][n] = dp[u][n];



    for(int i = n - 1; i >= 1; i--) {
        suf[u][i] = min(suf[u][i + 1],dp[u][i]);
    }
}

int main() {
    cin >> n;

    vector<int> v;

    for(int i = 1; i <= n; i++) {
        int bap;
        scanf("%d %d %lld",&bap,&h[i],&c[i]);
        if(bap != i) adj[bap].push_back(i);
        v.push_back(h[i]);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());

    for(int i = 1; i <= n; i++) {
        h[i] = lower_bound(v.begin(),v.end(),h[i]) - v.begin() + 1;
    }

    dfs(1);

    cout<<suf[1][1]<<endl;







}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d %lld",&bap,&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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