제출 #344777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344777		Gurban	Biochips (IZhO12_biochips)	C++17	0 / 100	4 ms	5116 KiB

biochips

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

using ll = long long;

const int N = 5e2+5;
const int maxn=2e5+5;
int n,m,root;
int p[maxn],a[maxn];
int mx[maxn],l[maxn],r[maxn];
vector<int>E[maxn],v;
int dp[maxn][N],ps[maxn];

void dfs(int nd){
	mx[nd] = a[nd],l[nd]=r[nd]=nd;
	for(auto i : E[nd]){
		dfs(i);
		if(l[nd] == nd) l[nd] = l[i];
		r[nd] = r[i];
		mx[nd] = max(mx[nd],mx[i]);
	}
}

void f(int pos,int nd){
	if(nd == 0 or r[nd] != v[pos]) return;
	int lft = ps[l[nd]] - 1;
	for(int i = 1;i <= min(m,lft + 1);i++)
		if(dp[lft][i-1] != -1 and dp[lft][i-1] + mx[nd] > dp[pos][i]) dp[pos][i] = dp[lft][i-1]+mx[nd];
	f(pos,p[nd]);
}

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

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

	assert((int)v.size()-1 >= m);

	for(int i = 0;i < (int)v.size();i++) for(int j = 1;j <= m;j++) dp[i][j] = -1;

	for(int i = 1;i < (int)v.size();i++){
		f(i,v[i]);
		for(int j = 1;j <= m;j++) dp[i][j] = max(dp[i][j],dp[i-1][j]);
	}
	cout<<dp[(int)v.size()-1][m];
}

• Subtask 1: 0 / 100