oj.uz

답안 #13261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13261 2015-02-06T19:12:40 Z baneling100 바이오칩 (IZhO12_biochips) C++
100 / 100
 223 ms 399928 KB 
#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;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 398872 KB Output is correct
2 Correct 0 ms 398872 KB Output is correct
3 Correct 0 ms 398872 KB Output is correct
4 Correct 3 ms 399004 KB Output is correct
5 Correct 5 ms 398872 KB Output is correct
6 Correct 6 ms 398872 KB Output is correct
7 Correct 122 ms 399928 KB Output is correct
8 Correct 116 ms 399928 KB Output is correct
9 Correct 209 ms 399796 KB Output is correct
10 Correct 223 ms 399796 KB Output is correct