제출 #672556

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
672556	2022-12-16 15:56:14	MohamedFaresNebili	Chase (CEOI17_chase)	C++14	100 / 100	308 ms	173648 KiB

chase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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