Submission #1197591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197591		miniob	Biochips (IZhO12_biochips)	C++20	60 / 100	80 ms	201800 KiB

biochips

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

int a[100007];
int dp[100007][507];
int k;

vector<int> synowie[100007];

void dfs(int s, int ojc)
{
	if (ojc != -1)
	{
		for (int i = 1; i <= k; i++)
		{
			dp[s][i] = dp[ojc][i];
		}
	}
	for (auto x : synowie[s])
	{
		dfs(x, s);
	}
	if (ojc != -1)
	{
		for (int i = k; i >= 1; i--)
		{
			dp[ojc][i] = max(dp[ojc][i], dp[s][i]);
			if (dp[ojc][i - 1] >= 0)
			{
				dp[ojc][i] = max(dp[ojc][i], dp[ojc][i - 1] + a[s]);
			}
		}
	}
	else
	{
		dp[s][1] = max(dp[s][1], a[1]);
	}
	/*cout << s << endl;
	for(int i = 0; i <= k; i++)
	{
		cout << dp[s][i] << " ";
	}
	cout << endl;*/
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, x;
	cin >> n >> k;
	for (int i = 0; i <= n + 3; i++)
	{
		for (int j = 1; j <= k + 2; j++)
		{
			dp[i][j] = -1;
		}
	}
	int wh = -1;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		if(x != 0)
		{
			synowie[x].push_back(i);
		}
		else
		{
			wh = i;
		}
		cin >> a[i];
	}
	dfs(wh, -1);
	cout << dp[wh][k] << endl;
	return 0;
}

• Subtask 1: 60 / 100