Submission #1300457

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

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