#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define pb push_back
#define sz size()
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll N = 2e5+10;
const ll mod=1e9+7;
const ll inf=1e9;
ll n,m;
vector <vector <ll>> g(N);
ll a[N],b[N],tin[N],p;
ll dp[N][505];
ll timer=1;
void dfs(ll v){
ll tt=timer;
for(auto to : g[v]) dfs(to);
tin[timer]=tt;
b[timer]=a[v];
timer++;
}
void solve(){
ll i,j,c=0;
cin>>n>>m;
for(i=1;i<=n;i++){
cin>>p>>a[i];
if(!b) {
c=i;
continue;
}
g[p].pb(i);
}
dfs(c);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
dp[i][j]=-inf;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[tin[i]-1][j-1]+b[i]);
}
}
cout<<dp[n][m]<<endl;
}
main(){
//fre("");
//start();
ll t=1;
//cin>>t;
while(t--)solve();
}
Compilation message
biochips.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
52 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
5020 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
5332 KB |
Output isn't correct |
| 4 |
Incorrect |
25 ms |
40532 KB |
Output isn't correct |
| 5 |
Incorrect |
26 ms |
45012 KB |
Output isn't correct |
| 6 |
Incorrect |
27 ms |
45032 KB |
Output isn't correct |
| 7 |
Runtime error |
275 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
277 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
284 ms |
524288 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
281 ms |
524288 KB |
Execution killed with signal 9 |
