oj.uz

답안 #363948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363948 2021-02-07T14:39:40 Z dolphingarlic Chase (CEOI17_chase) C++14
100 / 100
 288 ms 153476 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n, k, p[100001];
vector<int> graph[100001];
ll dp1[100001][101], dp2[100001][101], ans = 0;

void dfs(int node = 1, int par = 0) {
	ll sm = 0;
	for (int i : graph[node]) sm += p[i];
	dp2[node][1] = sm;
	for (int i : graph[node]) if (i != par) {
		dfs(i, node);
		for (int j = 1; j <= k; j++) ans = max(ans, dp2[node][j] + dp1[i][k - j]);
		for (int j = 1; j <= k; j++) {
			dp1[node][j] = max({dp1[node][j], dp1[i][j], dp1[i][j - 1] + sm - p[par]});
			dp2[node][j] = max({dp2[node][j], dp2[i][j], dp2[i][j - 1] + sm - p[i]});
		}
	}
	fill(dp2[node] + 1, dp2[node] + k + 1, 0);
	dp2[node][1] = sm;
	reverse(graph[node].begin(), graph[node].end());
	for (int i : graph[node]) if (i != par) {
		for (int j = 1; j <= k; j++) ans = max(ans, dp2[node][j] + dp1[i][k - j]);
		for (int j = 1; j <= k; j++)
			dp2[node][j] = max({dp2[node][j], dp2[i][j], dp2[i][j - 1] + sm - p[i]});
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> p[i];
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs();
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 4 ms 3948 KB Output is correct
8 Correct 3 ms 3948 KB Output is correct
9 Correct 3 ms 3564 KB Output is correct
10 Correct 4 ms 4204 KB Output is correct
11 Correct 4 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 131180 KB Output is correct
2 Correct 237 ms 131052 KB Output is correct
3 Correct 222 ms 85860 KB Output is correct
4 Correct 170 ms 151532 KB Output is correct
5 Correct 288 ms 153476 KB Output is correct
6 Correct 283 ms 153452 KB Output is correct
7 Correct 278 ms 153068 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 4 ms 3948 KB Output is correct
8 Correct 3 ms 3948 KB Output is correct
9 Correct 3 ms 3564 KB Output is correct
10 Correct 4 ms 4204 KB Output is correct
11 Correct 4 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 238 ms 131180 KB Output is correct
14 Correct 237 ms 131052 KB Output is correct
15 Correct 222 ms 85860 KB Output is correct
16 Correct 170 ms 151532 KB Output is correct
17 Correct 288 ms 153476 KB Output is correct
18 Correct 283 ms 153452 KB Output is correct
19 Correct 278 ms 153068 KB Output is correct
20 Correct 281 ms 153452 KB Output is correct
21 Correct 111 ms 85356 KB Output is correct
22 Correct 276 ms 153452 KB Output is correct
23 Correct 174 ms 151532 KB Output is correct
24 Correct 280 ms 153324 KB Output is correct
25 Correct 187 ms 85860 KB Output is correct
26 Correct 250 ms 131308 KB Output is correct
27 Correct 248 ms 131180 KB Output is correct