Submission #339096

#	Time	Username	Problem	Language	Result	Execution time	Memory
339096		fixikmila	Biochips (IZhO12_biochips)	C++14	0 / 100	2094 ms	146980 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>graph[200000];
int dp[200000][501],a[200000];
bool used[200000];
int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0;
void dfs(ll v,ll p=-1){
    used[v]=true;
    if(graph[v].size()==1){
            dp[v][1]=a[v];
            return;
    }

    for(auto u : graph[v]){
        if(used[u])continue;
        dfs(u,v);
    }
        for(auto u : graph[v]){
            if(u==p)continue;
            vector<ll>c(m+1);
            for(int j=0;j<=m;j++){

                    for(int i=j;i<=m;i++){
                            //if(v==2&&u==4&&i==2)cout<<j<<" "<<dp[4][1]<<dp[2]<<"ss"<<endl;
                        c[i]=max(ll(dp[v][i-j]+dp[u][j]),c[i]);
                    }

            }
            for(int z=m;z>=0;z--){
                dp[v][z]=c[z];
            }
        }
        dp[v][1]=a[v];
    for(auto u : graph[v]){
        if(u==p)continue;
        dp[v][1]=max(dp[v][1],dp[u][1]);
    }
}
int main()
{
    //freopen("stones.in","r",stdin);
    //freopen("stones.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin>>n>>m;
    for(int i=0;i<n;i++){
            cin>>x>>y;
            x--;
            a[i]=y;
            if(x==-1){
                z=i;
                continue;
            }
        graph[i].push_back(x);
        graph[x].push_back(i);
    }
    dfs(z);
    ans=dp[z][m];
    //cout<<dp[2][2]<<endl;
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 100