Submission #1299991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299991		Petrix	Biochips (IZhO12_biochips)	C++20	100 / 100	274 ms	393116 KiB

biochips

#include<iostream>
#include<vector>
using namespace std;

int val[200001],m,t;
vector<int> v[200001];
int dp[200001][501];
int aux[200001];

void dfs(int nod){
    int i;
    aux[nod]=t;
    for(auto it:v[nod]) dfs(it);
    for(i=1;i<=m;i++){
        dp[t+1][i]=max(dp[t][i],dp[aux[nod]][i-1]+val[nod]);
    }
    t++;
}

int main()
{
    int n,aux1,a,i;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>a>>val[i];
        if(!a) aux1=i;
        else v[a].push_back(i);
    }
    for(i=1;i<=m;i++) dp[0][i]=-1e9;
    dfs(aux1);
    cout<<dp[n][m]<<"\n";
}

• Subtask 1: 100 / 100