제출 #1300456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300456		MinhKien	바이오칩 (IZhO12_biochips)	C++20	60 / 100	2105 ms	213608 KiB

biochips

#include <iostream>
#include <vector>

using namespace std;

const int N = 2e5 + 10;
const int M = 510;

int n, k, u, a[N];
int root, dp[N][M];
vector <int> v[N];

void DFS(int s) {
    for (int z: v[s]) {
        DFS(z);

        for (int i = k; i >= 1; --i) {
            for (int j = 1; j <= i; ++j) {
                dp[s][i] = max(dp[s][i], dp[s][i - j] + dp[z][j]);
            }
        }

        for (int i = 1; i <= k; ++i) {
            dp[s][i] = max(dp[s][i], dp[z][i]);
        }
    }

    dp[s][1] = max(dp[s][1], a[s]);
}

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> u >> a[i];
        if (u == 0) root = i;
        else v[u].push_back(i);
    }

    DFS(root);

    cout << dp[root][k] << "\n";

    return 0;
}

• Subtask 1: 60 / 100