Submission #89226

#TimeUsernameProblemLanguageResultExecution timeMemory
89226turbatBiochips (IZhO12_biochips)C++14
0 / 100
7 ms4984 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define F first #define S second #define N 200005 #define M 505 int dp[N][M], pr[N], n, m, s[N], cnt, in[N], out[N], l, r, now, ans; vector <int> child[N], ve; void dfs(int x){ if (child[x].size()) cnt++; in[x] = cnt; for (auto a : child[x]) dfs(a); ve.pb(x); out[x] = cnt; } int main (){ cin >> n>> m; for (int i = 1;i <= n;i++){ cin >> pr[i]>> s[i]; child[pr[i]].pb(i); } dfs(child[0][0]); for (auto x : ve){ l = in[x]; r = out[x]; for (int i = 1;i <= r;i++) dp[r][i] = max(dp[r][i], dp[r - 1][i]); for (int i = 1;i <= l;i++) dp[r][i] = max(dp[r][i], dp[l - 1][i - 1] + s[x]); } cout << dp[cnt][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...