# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1114134 | 0pt1mus23 | Biochips (IZhO12_biochips) | C++14 | 2088 ms | 268872 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e5 +23, inf = LLONG_MAX, LG = 20;
vector<int> graph[sze];
int val[sze];
int k;
int dp[sze][501];
int mx[sze];
void dfs(int node,int par=-1){
int a= 0;
for(auto v:graph[node]){
if(v!=par){
dfs(v,node);
int b = mx[v];
for(int i = a;i>=0;i--){
if( (!i) || dp[node][i]){
for(int j= 0;j<=b;j++){
if(!(j) || dp[v][j]){
dp[node][i+j]=max(dp[node][i+j],dp[node][i] + dp[v][j]);
}
}
}
}
a+=b;
mx[node]=max(mx[node],a);
}
}
dp[node][1]=max(dp[node][1],val[node]);
mx[node]=max(mx[node],(int)1);
}
void fast(){
int n;
cin>>n>>k;
int root =0;
for(int i=1;i<=n;i++){
int p,w;
cin>>p>>w;
root|=(!p) * i;
if(p!=0){
graph[p].pb(i);
graph[i].pb(p);
}
val[i]=w;
}
dfs(root);
cout<<dp[root][k]<<endl;
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |