제출 #1027715

#제출 시각아이디문제언어결과실행 시간메모리
1027715vjudge1Chase (CEOI17_chase)C++17
40 / 100
4066 ms336224 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+5, V = 1e2+2; int n, v, ans, a[N], sum[N], dp[2][2][V][N]; pair<int, int> edge[N]; vector<pair<int, int>> adj[N]; int dfs(int f, int d, int nwV, int e) { if (dp[f][d][nwV][e] != -1) return dp[f][d][nwV][e]; dp[f][d][nwV][e] = 0; int x = edge[e].first; int y = edge[e].second; if (d) swap(x, y); // estoy en x y vengo de y // lanzo pan if (nwV) { for (auto& [z, idx] : adj[x]) { if (f && z == y) continue; int nwD = (edge[idx].first == z ? 0 : 1); dp[f][d][nwV][e] = max(dp[f][d][nwV][e], sum[x] - (!f ? 0 : a[y]) + dfs(1, nwD, nwV-1, idx)); } } // no lanzo pan for (auto& [z, idx] : adj[x]) { if (f && z == y) continue; int nwD = (edge[idx].first == z ? 0 : 1); dp[f][d][nwV][e] = max(dp[f][d][nwV][e], dfs(1, nwD, nwV, idx)); } return dp[f][d][nwV][e]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> v; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n-1; i++) { int x, y; cin >> x >> y; x--; y--; adj[x].push_back(make_pair(y, i)); adj[y].push_back(make_pair(x, i)); edge[i] = make_pair(x, y); } memset(sum, 0, sizeof(sum)); for (int i = 0; i < n; i++) { for (auto& [j, idx] : adj[i]) { sum[i] += a[j]; } } for (int i = 0; i < n-1; i++) { for (int j = 0; j <= v; j++) { dp[0][0][j][i] = dp[0][1][j][i] = dp[1][0][j][i] = dp[1][1][j][i] = -1; } } for (int i = 0; i < n-1; i++) { dfs(0, 0, v, i); dfs(0, 1, v, i); } ans = 0; for (int i = 0; i < n-1; i++) { for (int j = 0; j <= v; j++) { ans = max({ans, dp[0][0][j][i], dp[0][1][j][i], dp[1][0][j][i], dp[1][1][j][i]}); } } cout << ans << "\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...