Submission #121640

#TimeUsernameProblemLanguageResultExecution timeMemory
121640pamajChase (CEOI17_chase)C++14
0 / 100
3 ms1280 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t const int maxn = 1e3 + 10; int v[maxn], p[maxn], n, t, dp[maxn][110]; vector<int> G[maxn]; int solve(int x, int y, int num) { if(dp[x][num] != -1) return dp[x][num]; if(num == 0) return 0; int best = 0; for(auto u : G[x]) { if(u == y) continue; int caso1 = solve(u, x, num); int caso2 = v[u] + -p[y] + solve(u, x, num - 1); best = max({best, caso1, caso2}); } return dp[x][num] = best; } int32_t main() { cin >> n >> t; for(int i = 1; i <= n; i++) { cin >> p[i]; } for(int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } for(int i = 1; i <= n; i++) { for(auto u : G[i]) { v[i] += p[u]; } } memset(dp, -1, sizeof(dp)); int ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, solve(i, 0, t)); //cout << i << " " << solve(i, i, t) << "\n"; } cout << ans << "\n"; for(int i = 1; i <= n; i++) { //cout << i << " " << v[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...