Submission #519347

#	Time	Username	Problem	Language	Result	Execution time	Memory
519347		hoanghq2004	Chase (CEOI17_chase)	C++14	0 / 100	119 ms	55200 KiB

chase

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int n, m;
int f[N][110];
int c[N];
vector <int> g[N];

void dfs(int u, int p) {
    int tot = 0;
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        tot += c[v];
    }
    f[u][1] = tot;
    for (auto v: g[u]) {
        if (v == p) continue;
        for (int i = 0; i <= m; ++i) {
            f[u][i] = max(f[u][i], f[v][i]);
            f[u][i + 1] = max(f[u][i + 1], f[v][i] + tot - c[v]);
        }
    }
    for (int i = 1; i <= m; ++i) f[u][i] = max(f[u][i], f[u][i - 1]);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << f[1][m];
}

Compilation message (stderr)

chase.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
chase.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30