oj.uz

Submission #928166

# Submission time Handle Problem Language Result Execution time Memory
928166 2024-02-15T23:44:45 Z vjudge1 Dostavljač (COCI18_dostavljac) C++17
140 / 140
 193 ms 6756 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 28 ms 6712 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6756 KB Output is correct
2 Correct 16 ms 6756 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6748 KB Output is correct
2 Correct 115 ms 6740 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6736 KB Output is correct
2 Correct 40 ms 6740 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 6740 KB Output is correct
2 Correct 19 ms 6744 KB Output is correct