제출 #1315714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315714		Jawad_Akbar_JJ	바이오칩 (IZhO12_biochips)	C++20	0 / 100	307 ms	523120 KiB

biochips

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<18;
vector<int> nei[N];
int dp[N][505], ch[N], cur, a[N], mem[N];

void dfs(int u){
	ch[u] = 1;
	for (int i : nei[u])
		dfs(i), ch[u] += ch[i];
	a[++cur] = 1;
}

int main(){
	int n, m;
	cin>>n>>m;

	for (int i=1, p;i<=n;i++){
		cin>>p>>mem[i];
		nei[p].push_back(i);
	}

	dfs(nei[0][0]);

	for (int i=0;i<N;i++){
		for (int j=1;j<=m;j++)
			dp[i][j] = -1e9;
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++)
			dp[i][j] = max(dp[i-1][j], dp[i - ch[a[i]]][j-1] + mem[a[i]]);
	}
	cout<<dp[n][m]<<'\n';
}

• Subtask 1: 0 / 100