# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
13261 | baneling100 | Biochips (IZhO12_biochips) | C++98 | 223 ms | 399928 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <vector>
#define N_MAX 200000
#define M_MAX 500
#define INF 0x7fffffff
using namespace std;
vector <int> Tree[N_MAX+1];
int N, M, K, Root, X[N_MAX+1], D[N_MAX+1][M_MAX+1], Before[N_MAX+1];
void input(void) {
int i, j;
scanf("%d %d",&N,&M);
for(i=1 ; i<=N ; i++) {
scanf("%d %d",&j,&X[i]);
if(j) Tree[j].push_back(i);
else Root=i;
}
for(i=1 ; i<=M ; i++)
D[0][i]=-INF;
}
void treeDP(int now) {
int i, j=Tree[now].size();
Before[now]=K;
for(i=0 ; i<j ; i++)
treeDP(Tree[now][i]);
K++;
for(i=1 ; i<=M ; i++)
D[K][i]=max(D[K-1][i],D[Before[now]][i-1]+X[now]);
}
int main(void) {
input();
treeDP(Root);
printf("%d",D[N][M]);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |