Submission #672556

#	Time	Username	Problem	Language	Result	Execution time	Memory
672556		MohamedFaresNebili	Chase (CEOI17_chase)	C++14	100 / 100	308 ms	173648 KiB

chase

#include <bits/stdc++.h>

            using namespace std;
            using ll = long long;

            #define int ll

            int res, N, K, P[100005];
            int X[100001][101], Y[100001][101];
            vector<int> adj[100005];

            void dfs(int v, int p) {
                int S = 0;
                for(auto u : adj[v]) S += P[u];
                X[v][1] = S;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v);
                    for(int i = 1; i <= K; i++) {
                        res = max(res, X[v][i] + Y[u][K - i]);
                        X[v][i] = max({X[v][i], X[v][i - 1], X[u][i], X[u][i - 1] + S - P[u]});
                        Y[v][i] = max({Y[v][i], Y[v][i - 1], Y[u][i], Y[u][i - 1] + S - P[p]});
                    }
                }

                reverse(adj[v].begin(), adj[v].end());
                memset(X[v], 0, sizeof X[v]);
                memset(Y[v], 0, sizeof Y[v]);
                X[v][1] = S;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    for(int i = 1; i <= K; i++) {
                        res = max(res, X[v][i] + Y[u][K - i]);
                        X[v][i] = max({X[v][i], X[v][i - 1], X[u][i], X[u][i - 1] + S - P[u]});
                        Y[v][i] = max({Y[v][i], Y[v][i - 1], Y[u][i], Y[u][i - 1] + S - P[p]});
                    }
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> K;
                for(int l = 1; l <= N; l++)
                    cin >> P[l];
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                dfs(1, 0);
                cout << res << "\n";
                return 0;
            }

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