oj.uz

Submission #333844

# Submission time Handle Problem Language Result Execution time Memory
333844 2020-12-07T22:49:49 Z limabeans Biochips (IZhO12_biochips) C++17
0 / 100
 2000 ms 15292 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 2e5+10;



int n, m;
vector<int> g[maxn];
int a[maxn];


vector<int> dp[maxn];



vector<int> merge(vector<int> v, vector<int> w) {
    int N = v.size();
    int M = w.size();
    vector<int> res(N+M,0);
    for (int i=0; i<N; i++) {
	for (int j=0; j<M; j++) {
	    res[i+j] = max(res[i+j], v[i]+w[j]);
	}
    }
    return res;
}

void dfs(int at) {
    dp[at].push_back(0);
    for (int to: g[at]) {
	dfs(to);
	dp[at] = merge(dp[at], dp[to]);
    }

    while ((int)dp[at].size()<2) dp[at].push_back(0);
    dp[at][1] = max(dp[at][1], a[at]);
}

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

    cin>>n>>m;
    int root = -1;
    for (int i=1; i<=n; i++) {
	int p; cin>>p;
	if (p==0) {
	    root=i;
	} else {
	    g[p].push_back(i);
	}
	cin>>a[i];
    }

    dfs(root);
    cout<<dp[root][m]<<endl;
    
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9836 KB Output is correct
4 Correct 105 ms 10880 KB Output is correct
5 Correct 159 ms 10952 KB Output is correct
6 Correct 154 ms 10860 KB Output is correct
7 Execution timed out 2084 ms 15292 KB Time limit exceeded
8 Halted 0 ms 0 KB -