oj.uz

Submission #59674

# Submission time Handle Problem Language Result Execution time Memory
59674 2018-07-22T21:48:44 Z thiago4532 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 97672 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 1e5 + 10, maxk = 1e2 + 10;
vector<int> grafo[maxn];
int n, k;
int gain[maxn], x[maxn], dp[maxn][maxk];

void dfs(int u, int p=0){
	gain[u] = 0;
	for(auto v : grafo[u]){
		if(v == p) continue;
		gain[u] += x[v];

		dfs(v, u);
	}
}

void solve(int u, int p=0){
	for(int l=0;l<=k;l++)
		dp[u][l] = 0;

	for(auto v : grafo[u]){
		if(v == p) continue;
		solve(v, u);

		for(int l=1;l<=k;l++)
			dp[u][l] = max({dp[u][l], dp[v][l], dp[v][l-1] + gain[u]});
	}
}

int32_t main(){
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> x[i];

	for(int i=1;i<n;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}

	int ans=0;
	for(int i=1;i<=n;i++){
		dfs(i);
		solve(i);
		// cout << "gain: " << gain[i] << "\n";
		// cout << "dp: " << dp[i][k] << "\n";
		ans = max(ans, dp[i][k]);
	}
	cout << ans << "\n";
	
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct
5 Correct 5 ms 3072 KB Output is correct
6 Correct 5 ms 3072 KB Output is correct
7 Correct 382 ms 3856 KB Output is correct
8 Correct 62 ms 3952 KB Output is correct
9 Correct 39 ms 3964 KB Output is correct
10 Correct 362 ms 4020 KB Output is correct
11 Correct 152 ms 4056 KB Output is correct
12 Correct 92 ms 4080 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 97672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2792 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct
5 Correct 5 ms 3072 KB Output is correct
6 Correct 5 ms 3072 KB Output is correct
7 Correct 382 ms 3856 KB Output is correct
8 Correct 62 ms 3952 KB Output is correct
9 Correct 39 ms 3964 KB Output is correct
10 Correct 362 ms 4020 KB Output is correct
11 Correct 152 ms 4056 KB Output is correct
12 Correct 92 ms 4080 KB Output is correct
13 Execution timed out 4054 ms 97672 KB Time limit exceeded
14 Halted 0 ms 0 KB -