oj.uz

Submission #238750

# Submission time Handle Problem Language Result Execution time Memory
238750 2020-06-12T15:19:32 Z MohamedAhmed04 Dostavljač (COCI18_dostavljac) C++14
140 / 140
 120 ms 2432 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 500 + 10 ;

int arr[MAX] , dp[MAX][MAX][2] , tmp[MAX][2] ;
int n , m ;

vector< vector<int> >adj(MAX) ;

void dfs(int node , int par)
{
	dp[node][0][0] = dp[node][0][1] = 0 ;
	dp[node][1][0] = dp[node][1][1] = arr[node] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node) ;
		for(int i = 0 ; i <= m ; ++i)
		{
			if(!dp[node][i][0] && i)
				break ;
			for(int j = 0 ; i + j + 1 <= m ; ++j)
			{
				if(!dp[child][j][0] && j)
					break ;
				int k = i+j+1 ;
				tmp[k+1][0] = max(tmp[k+1][0] , dp[node][i][0] + dp[child][j][0]) ;
				tmp[k][1] = max(tmp[k][1] , dp[node][i][0] + max(dp[child][j][0] , dp[child][j][1])) ;
				tmp[k+1][1] = max(tmp[k+1][1] , dp[node][i][1] + dp[child][j][0]) ;
			}
		}
		int now0 = 0 , now1 = 0 ;
		for(int i = 0 ; i <= m ; ++i)
		{
			now0 = max(now0 , max(dp[node][i][0] , tmp[i][0])) ;
			now1 = max(now1 , max(dp[node][i][1] , tmp[i][1])) ;
			dp[node][i][0] = now0 ;
			dp[node][i][1] = now1 ;
			tmp[i][0] = tmp[i][1] = 0 ;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	dfs(1 , -1) ;
	return cout<<max(dp[1][m][0] , dp[1][m][1])<<"\n" , 0 ;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 6 ms 768 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 13 ms 1024 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1144 KB Output is correct
2 Correct 12 ms 1152 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1664 KB Output is correct
2 Correct 29 ms 1656 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 1912 KB Output is correct
2 Correct 22 ms 1920 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2424 KB Output is correct
2 Correct 9 ms 2432 KB Output is correct