oj.uz

Submission #394791

# Submission time Handle Problem Language Result Execution time Memory
394791 2021-04-27T10:15:23 Z Nima_Naderi Chase (CEOI17_chase) C++14
100 / 100
 806 ms 169052 KB 
//In the name of God
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 5;
const ll MXM = 100 + 5;
ll n, k, ans;
ll dp[MXM][MXN], pd[MXM][MXN], fp[MXM];
ll P[MXN], N[MXN], F[MXN];
vector<ll> adj[MXN];
void DFS(ll u, ll par){
	pd[1][u] = N[u];
	F[u] = N[u] - P[par];
	for(auto v : adj[u]) if(v != par) DFS(v, u);
	for(auto v : adj[u]){
		if(v != par){
			memset(fp, 0, sizeof fp);
			for(int j = 0; j <= k; j ++){
				fp[j] = max(fp[j], pd[j][v]);
				if(j) fp[j] = max(fp[j], pd[j - 1][v] + N[u] - P[v]);
			}
			for(int j = 0; j <= k; j ++) ans = max(ans, fp[j] + dp[k - j][u]);
			for(int j = 0; j <= k; j ++) pd[j][u] = max(pd[j][u], fp[j]);
			for(int j = 0; j <= k; j ++) dp[j][u] = max(dp[j][u], dp[j][v]);
		}
	}
	if(adj[u].size() > 1){
		reverse(adj[u].begin(), adj[u].end());
		for(int j = 0; j <= k; j ++) dp[j][u] = 0;
		for(auto v : adj[u]){
			if(v != par){
				memset(fp, 0, sizeof fp);
				for(int j = 0; j <= k; j ++){
					fp[j] = max(fp[j], pd[j][v]);
					if(j) fp[j] = max(fp[j], pd[j - 1][v] + N[u] - P[v]);
				}
				for(int j = 0; j <= k; j ++) ans = max(ans, fp[j] + dp[k - j][u]);
				for(int j = 0; j <= k; j ++) dp[j][u] = max(dp[j][u], dp[j][v]);
			}
		}
	}
	for(int j = 0; j < k; j ++){
		ans = max(ans, N[u] + dp[j][u]);
	}
	for(auto v : adj[u]){
		if(v != par){
			for(int j = 1; j <= k; j ++){
				dp[j][u] = max(dp[j][u], dp[j - 1][v] + F[u]);
			}
		}
	}
	dp[1][u] = max(dp[1][u], F[u]);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> P[i];
	for(int i = 1; i < n; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
		N[u] += P[v], N[v] += P[u];
	}
	DFS(1, 0);
	for(int i = 1; i <= n; i ++) ans = max(ans, dp[k][i]);
	for(int i = 1; i <= n; i ++) ans = max(ans, pd[k][i]);
	cout << ans << '\n';
	return 0;
}
//! N.N

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 6 ms 4684 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 6 ms 5324 KB Output is correct
11 Correct 4 ms 3532 KB Output is correct
12 Correct 3 ms 2928 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 97828 KB Output is correct
2 Correct 456 ms 97740 KB Output is correct
3 Correct 230 ms 14516 KB Output is correct
4 Correct 128 ms 14088 KB Output is correct
5 Correct 777 ms 167396 KB Output is correct
6 Correct 794 ms 168884 KB Output is correct
7 Correct 797 ms 168728 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 6 ms 4684 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 6 ms 5324 KB Output is correct
11 Correct 4 ms 3532 KB Output is correct
12 Correct 3 ms 2928 KB Output is correct
13 Correct 427 ms 97828 KB Output is correct
14 Correct 456 ms 97740 KB Output is correct
15 Correct 230 ms 14516 KB Output is correct
16 Correct 128 ms 14088 KB Output is correct
17 Correct 777 ms 167396 KB Output is correct
18 Correct 794 ms 168884 KB Output is correct
19 Correct 797 ms 168728 KB Output is correct
20 Correct 793 ms 169052 KB Output is correct
21 Correct 100 ms 13856 KB Output is correct
22 Correct 806 ms 168872 KB Output is correct
23 Correct 94 ms 13892 KB Output is correct
24 Correct 788 ms 168992 KB Output is correct
25 Correct 227 ms 13224 KB Output is correct
26 Correct 414 ms 97828 KB Output is correct
27 Correct 416 ms 97904 KB Output is correct