Submission #352335

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
352335	2021-01-20T15:41:15 Z	rqi	Biochips (IZhO12_biochips)	C++14	100 / 100	600 ms	21484 KB

biochips

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second
#define mp make_pair

#define sz(x) (int)(x).size()

const int mx = 200005;
int N, M;
vi children[mx];
int x[mx];
vi dp[mx];

void genDP(int node){
	dp[node] = vi{0};
	for(auto u: children[node]){
		genDP(u);

		vi res = vi(min(M+1, sz(dp[node])+sz(dp[u])-1), 0);
		for(int i = 0; i < sz(dp[node]); i++){
			for(int j = 0; j < min(M+1-i, sz(dp[u])); j++){
				res[i+j] = max(res[i+j], dp[node][i]+dp[u][j]);
			}
		}
		dp[node] = res;
	}

	if(sz(dp[node]) < 2){
		dp[node].pb(0);
	}

	dp[node][1] = max(dp[node][1], x[node]);
}

int main(){
	cin >> N >> M;

	for(int i = 1; i <= N; i++){
		int p;
		cin >> p >> x[i];
		children[p].pb(i);
	}

	genDP(0);

	cout << dp[0][M] << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9708 KB	Output is correct
2	Correct	7 ms	9708 KB	Output is correct
3	Correct	7 ms	9708 KB	Output is correct
4	Correct	14 ms	10348 KB	Output is correct
5	Correct	16 ms	10348 KB	Output is correct
6	Correct	15 ms	10348 KB	Output is correct
7	Correct	278 ms	18284 KB	Output is correct
8	Correct	273 ms	18028 KB	Output is correct
9	Correct	464 ms	20460 KB	Output is correct
10	Correct	600 ms	21484 KB	Output is correct