Submission #346340

#	Time	Username	Problem	Language	Result	Execution time	Memory
346340		nicolaalexandra	바이오칩 (IZhO12_biochips)	C++14	0 / 100	42 ms	23020 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){

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

    if (L[nod].empty()) /// frunza
        cnt[nod] = 1;

    dp[nod][0] = 0;

    for (auto vecin : L[nod]){

        for (int i=1;i<=cnt[nod];i++)
            aux[i] = 0;

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

        for (int i=1;i<=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=0;j<=m;j++)
            dp[i][j] = -INF;

    dfs (rad);

    cout<<dp[rad][m];

    return 0;
}

• Subtask 1: 0 / 100