Submission #574451

#	Time	Username	Problem	Language	Result	Execution time	Memory
574451		saarang123	Biochips (IZhO12_biochips)	C++17	60 / 100	2109 ms	399432 KiB

biochips

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

const int MXN = 200 * 1000 + 3;
const int MXM = 503;
int dp[MXN][MXM], a[MXN], sz[MXN];
vector<int> g[MXN];
int n, m;

void dfs(int v) {
	sz[v] = max(1, (int) g[v].size());
	for(int u : g[v]) {
		dfs(u);
		for(int i = sz[v]; i >= 0; i--)
			for(int j = 0; j <= sz[u]; j++) if(i + j <= m && dp[v][i] != -1 && dp[u][j] != -1)
				dp[v][i + j] = max(dp[v][i + j], dp[v][i] + dp[u][j]);
		sz[v] += sz[u];
	}
	dp[v][1] = max(dp[v][1], a[v]);
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    cin >> n >> m;
    int r = -1;
    for(int p, i = 1; i <= n; i++) {
    	cin >> p >> a[i];
    	dp[i][0] = 0;
    	for(int j = 1; j <= m; j++)
    		dp[i][j] = -1;
    	if(p) {
    		g[p].push_back(i);
    	}
    	else
    		r = i;
    }
    dfs(r);
    // for(int i = 1; i <= n; i++) {
    // 	for(int j = 1; j <= m; j++) 
    // 		cout << dp[i][j] << ' ';
    // 	cout << '\n';
    // }
    cout << dp[r][m] << '\n';
    return 0;
}

• Subtask 1: 60 / 100