Submission #346342

#	Time	Username	Problem	Language	Result	Execution time	Memory
346342		nicolaalexandra	Biochips (IZhO12_biochips)	C++14	100 / 100	755 ms	406536 KiB

biochips

#include <bits/stdc++.h>
#define DIM 200010
#define DIMM 510
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
int dp[DIM][DIMM],v[DIM],cnt[DIM],aux[DIM];
int n,m,i,j,x,rad;

void dfs (int nod){

    cnt[nod] = 1;
    for (auto vecin : L[nod]){
        dfs (vecin);
        cnt[nod] += cnt[vecin];
    }

    for (auto vecin : L[nod]){

        for (int i=1;i<=min(m,cnt[nod]);i++)
            aux[i] = -INF;

        for (int i=1;i<=min(m,cnt[vecin]);i++) /// cat elimin din subarborele asta
            for (int j=min(m,cnt[nod]);j>=i;j--)
                if (dp[nod][j-i] >= 0 && dp[vecin][i] >= 0)
                    aux[j] = max (aux[j],dp[nod][j-i] + dp[vecin][i]);

        for (int i=1;i<=min(m,cnt[nod]);i++)
            dp[nod][i] = max (dp[nod][i],aux[i]);
    }

    dp[nod][1] = max(dp[nod][1],v[nod]);

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>x>>v[i];
        if (x)
            L[x].push_back(i);
        else rad = i;
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            dp[i][j] = -INF;

    dfs (rad);

    cout<<dp[rad][m];

    return 0;
}

• Subtask 1: 100 / 100