Submission #16861

#TimeUsernameProblemLanguageResultExecution timeMemory
16861muratBiochips (IZhO12_biochips)C++98
100 / 100
235 ms480144 KiB
#include <bits/stdc++.h> using namespace std; #define dbgs(x) cerr << (#x) << " --> " << (x) << ' ' #define dbg(x) cerr << (#x) << " --> " << (x) << endl #define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++) #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++) #define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--) #define type(x) __typeof(x.begin()) #define orta (bas + son >> 1) #define sag (k + k + 1) #define sol (k + k) #define pb push_back #define mp make_pair #define nd second #define st first #define endl '\n' typedef pair < int ,int > pii; typedef long long ll; const long long linf = 1e18+5; const int mod = (int) 1e9 + 7; const int logN = 17; const int inf = 1e9 + 7; const int N = 2e5 + 10; int w[N], val[N], n, m, x, y, start[N], finish[N], T, dp[N][600], root, p[N]; vector< int > v[N]; int dfs(int node) { start[node] = ++T; w[T] = node; foreach(it, v[node]) dfs(*it); finish[node] = T; } int main() { scanf("%d %d", &n, &m); FOR(i, 1, n) { scanf("%d %d", &x, &val[i]); if(!x) root = i; else v[x].pb(i); } dfs(root); FOR(i, 1, m) dp[n+1][i] = -inf; ROF(i, n, 1) FOR(j, 0, m) dp[i][j] = max(dp[i+1][j], (j != 0) * (dp[finish[w[i]] + 1][j-1] + val[w[i]])); printf("%d\n", dp[1][m]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...