Submission #1236031

#TimeUsernameProblemLanguageResultExecution timeMemory
1236031inesfiMagic Tree (CEOI19_magictree)C++20
34 / 100
2096 ms51272 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int TAILLEMAXI=100*1000+2,JOURSMAXI=22;
vector<int> enfants[TAILLEMAXI];
int bonus_fruit[TAILLEMAXI];
int jour_fruit[TAILLEMAXI];
int cb_par_jour[TAILLEMAXI][JOURSMAXI];
int memo[TAILLEMAXI][JOURSMAXI];

int cbjour(int a,int jour){
    int compt=0;
    if (jour_fruit[a]==jour){
        compt+=bonus_fruit[a];
    }
    for (auto v:enfants[a]){
        compt+=cbjour(v,jour);
    }
    cb_par_jour[a][jour]=compt;
    return compt;
}

int dp(int a,int jourmax){
    if (memo[a][jourmax]!=-1){
        return memo[a][jourmax];
    }
    if (enfants[a].size()==0){
        if (jour_fruit[a]<=jourmax){
            memo[a][jourmax]=bonus_fruit[a];
            return bonus_fruit[a];
        }
        memo[a][jourmax]=0;
        return 0;
    }
    int val1=0,val2=0;
    for (auto v:enfants[a]){
        val1+=dp(v,jourmax);
        val2+=dp(v,jour_fruit[a]);
    }
    int rep=0;
    if (jour_fruit[a]<=jourmax){
        //val2+=cb_par_jour[a][jour_fruit[a]];
        val2+=bonus_fruit[a];
        rep=val2;
    }
    rep=max(rep,val1);
    memo[a][jourmax]=rep;
    //cout<<a<<" "<<jourmax<<" "<<rep<<endl;
    return rep;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbnoeuds,nbfruits,nbjoursmaxi;
    cin>>nbnoeuds>>nbfruits>>nbjoursmaxi;
    for (int i=2;i<=nbnoeuds;i++){
        int val;
        cin>>val;
        enfants[val].push_back(i);
    }
    for (int i=0;i<nbfruits;i++){
        int s,j,w;
        cin>>s>>j>>w;
        bonus_fruit[s]=w;
        jour_fruit[s]=j;
    }
    for (int i=1;i<=nbjoursmaxi;i++){
        cbjour(1,i);
    }
    int rep=0;
    for (int i=1;i<=nbnoeuds;i++){
        for (int j=1;j<JOURSMAXI;j++){
            memo[i][j]=-1;
        }
    }
    for (auto i:enfants[1]){
        rep+=dp(i,JOURSMAXI-1);
    }
    cout<<rep<<endl;
    /*for (int i=1;i<=nbnoeuds;i++){
        for (int j=1;j<=nbjoursmaxi;j++){
            cout<<cb_par_jour[i][j]<<" ";
        }
        cout<<endl;
    }*/
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...