제출 #928166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928166		vjudge1	Dostavljač (COCI18_dostavljac)	C++17	140 / 140	193 ms	6756 KiB

dostavljac

#include<bits/stdc++.h>
using namespace std;
int n,m,tot = 0;
struct node
{
	int to,nxt;
}tree[1010];
int head[1010],a[1005],dp[3][1010][1010];
inline void add_edge(int u,int v)
{
	tree[++tot] = (node){v,head[u]};
	head[u] = tot;
}
inline void dfs(int u,int fa)
{
	dp[0][u][1] = a[u];
	dp[1][u][1] = a[u];
	for(int x = 2;x <= m;x++)
	{
		dp[1][u][x] = max(dp[1][u][x - 1],dp[1][u][x]);
		dp[0][u][x] = max(dp[0][u][x - 1],dp[0][u][x]);
	}
	for(int i = head[u];i;i = tree[i].nxt)
	{
		int v = tree[i].to;
		if(v == fa)
		{
			continue;
		}
		dfs(v,u);
		for(int x = m;x >= 1;x--)
		{
			for(int k = 1;k <= x;k++)
			{
				dp[0][u][x] = max(dp[0][u][x],dp[1][u][x - k] + dp[0][v][k - 1]);
				if(k >= 2)
				{
					dp[1][u][x] = max(dp[1][u][x],dp[1][u][x - k] + dp[1][v][k - 2]);
					dp[0][u][x] = max(dp[0][u][x],dp[0][u][x - k] + dp[1][v][k - 2]);
				}
			}
		}
	}
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i < n;i++)
	{
		int u,v;
		cin >> u >> v;
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs(1,1);
	cout << max(dp[0][1][m],dp[1][1][m]);
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14