oj.uz

Submission #363946

# Submission time Handle Problem Language Result Execution time Memory
363946 2021-02-07T14:38:25 Z dolphingarlic Chase (CEOI17_chase) C++14
100 / 100
 304 ms 155584 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 parent = 0) {
    ll c_sum = 0;
    for (int i : graph[node]) c_sum += p[i];
    dp2[node][1] = c_sum;
    for (int i : graph[node]) if (i != parent) {
        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] + c_sum - p[parent]});
            dp2[node][j] = max({dp2[node][j], dp2[i][j], dp2[i][j - 1] + c_sum - p[i]});
        }
    }
    fill(dp2[node] + 1, dp2[node] + k + 1, 0);
    dp2[node][1] = c_sum;
    reverse(graph[node].begin(), graph[node].end());
    for (int i : graph[node]) if (i != parent) {
        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] + c_sum - 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 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 4 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 3 ms 4204 KB Output is correct
12 Correct 4 ms 4204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 132588 KB Output is correct
2 Correct 261 ms 132460 KB Output is correct
3 Correct 195 ms 87268 KB Output is correct
4 Correct 173 ms 152940 KB Output is correct
5 Correct 282 ms 154988 KB Output is correct
6 Correct 290 ms 154860 KB Output is correct
7 Correct 302 ms 154476 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 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 4 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 3 ms 4204 KB Output is correct
12 Correct 4 ms 4204 KB Output is correct
13 Correct 246 ms 132588 KB Output is correct
14 Correct 261 ms 132460 KB Output is correct
15 Correct 195 ms 87268 KB Output is correct
16 Correct 173 ms 152940 KB Output is correct
17 Correct 282 ms 154988 KB Output is correct
18 Correct 290 ms 154860 KB Output is correct
19 Correct 302 ms 154476 KB Output is correct
20 Correct 289 ms 155584 KB Output is correct
21 Correct 121 ms 87532 KB Output is correct
22 Correct 304 ms 155476 KB Output is correct
23 Correct 181 ms 153580 KB Output is correct
24 Correct 286 ms 155500 KB Output is correct
25 Correct 188 ms 87692 KB Output is correct
26 Correct 253 ms 133356 KB Output is correct
27 Correct 253 ms 133356 KB Output is correct