Submission #1092445

#TimeUsernameProblemLanguageResultExecution timeMemory
1092445juicyBiochips (IZhO12_biochips)C++17
80 / 100
281 ms403540 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 2e5 + 5; int n, m; int a[N], L[N], R[N], pos[N], dp[N][505]; vector<int> g[N]; int timer; void dfs(int u) { pos[L[u] = ++timer] = u; for (int v : g[u]) { dfs(v); } R[u] = timer; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; int rt = -1; for (int i = 1; i <= n; ++i) { int pr; cin >> pr >> a[i]; if (!pr) { rt = i; } else { g[pr].push_back(i); } } dfs(rt); for (int i = 1; i <= n; ++i) { int u = pos[i]; for (int j = 0; j <= m; ++j) { dp[R[u] + 1][j + 1] = max(dp[R[u] + 1][j + 1], dp[i][j] + a[u]); dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); } } cout << dp[n][m]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...