Submission #1206153

#TimeUsernameProblemLanguageResultExecution timeMemory
1206153friendiksChase (CEOI17_chase)C++20
40 / 100
4097 ms96528 KiB
#ifndef LOCAL #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC diagnostic ignored "-Wpedantic" #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rnd(52); template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename V> using table = gp_hash_table<T, V>; using i128 = __int128; using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; const ll INF = 2e18; const int inf = 2e9; const int maxn = 1e5 + 7; const int maxk = 107; const int MOD = 1e9 + 7; const ld pi = acos(-1); const int P = 5167; const int L = 26; const ld EPS = 1e-7; template<typename T, typename V> void fill(T &container, V value) { for (auto &c : container) c = value; } #define int ll int cnt[maxn]; int price[maxn]; int dp[maxn][maxk]; int p[maxn]; vector<int> g[maxn]; void dfs(int v, int par = -1) { p[v] = par; dp[v][0] = 0; for (auto to : g[v]) { if (to == p[v]) continue; dfs(to, v); price[v] += cnt[to]; for (int k = 0; k < maxk; ++k) { dp[v][k] = max(dp[v][k], dp[to][k]); } } for (auto to : g[v]) { if (to == p[v]) continue; int d = 0; for (int k = 1; k < maxk; ++k) { d = max(d, dp[to][k - 1] + price[v]); dp[v][k] = max(dp[v][k], d); } } } void solve() { int n, k; cin >> n >> k; for (int i = 0; i < maxn; ++i) { for (int j = 0; j < maxk; ++j) { dp[i][j] = -INF; } } for (int i = 1; i <= n; ++i) cin >> cnt[i]; for (int i = 1; i < n; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } int mx = 0; for (int i = 1; i <= n; ++i) { for (int k = 1; k <= n; ++k) { price[k] = 0; for (int j = 0; j < maxk; ++j) { dp[k][j] = -INF; } } dfs(i); mx = max(mx, dp[i][k]); } cout << mx; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(4); int t = 1; //cin >> t; while (t--) solve(); //stress(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...