Submission #1300448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300448		MinhKien	Biochips (IZhO12_biochips)	C++20	50 / 100	397 ms	399632 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 - 1; i >= 1; --i) {
            dp[s][i + 1] = max(dp[s][i + 1], dp[s][i] + dp[z][1]);
        }

        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() {
    // freopen("input.txt", "r", stdin);

    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: 50 / 100