Submission #333844

#	Time	Username	Problem	Language	Result	Execution time	Memory
333844		limabeans	Biochips (IZhO12_biochips)	C++17	0 / 100	2084 ms	15292 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 2e5+10;



int n, m;
vector<int> g[maxn];
int a[maxn];


vector<int> dp[maxn];



vector<int> merge(vector<int> v, vector<int> w) {
    int N = v.size();
    int M = w.size();
    vector<int> res(N+M,0);
    for (int i=0; i<N; i++) {
	for (int j=0; j<M; j++) {
	    res[i+j] = max(res[i+j], v[i]+w[j]);
	}
    }
    return res;
}

void dfs(int at) {
    dp[at].push_back(0);
    for (int to: g[at]) {
	dfs(to);
	dp[at] = merge(dp[at], dp[to]);
    }

    while ((int)dp[at].size()<2) dp[at].push_back(0);
    dp[at][1] = max(dp[at][1], a[at]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    int root = -1;
    for (int i=1; i<=n; i++) {
	int p; cin>>p;
	if (p==0) {
	    root=i;
	} else {
	    g[p].push_back(i);
	}
	cin>>a[i];
    }

    dfs(root);
    cout<<dp[root][m]<<endl;
    
    return 0;
}

• Subtask 1: 0 / 100