Submission #1300628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300628		azik21	Biochips (IZhO12_biochips)	C++20	60 / 100	331 ms	589824 KiB

biochips

#include<iostream>
// #include<bits/stdc++.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#define pb push_back
#define ll long long 
#define all(v) (v).begin() , (v).end()
using namespace std;
const int N = 2e5+1 , inf = 1e9;
ll dp[N][502] ;
int  x[N] , n , k ;
int tin[N] , tout[N] , timer = 0 ;
pair<int ,int >q[N];
vector<int>g[N];
void dfs(int v , int p ){
    tin[v] = ++timer;

    for(auto it:g[v]){
        dfs(it , v);
    }
    tout[v] = ++timer;
    q[timer] = {x[v] , tin[v]};
}
signed main(){
    // freopen("d.in" , "r" , stdin);
    // freopen("d.out" , "w" , stdout);
    ios_base::sync_with_stdio(0) , cin.tie(0);
    cin >> n >> k;
    int pr =0 ;
    for(int i= 1; i <= n ; i++){
        int p;
        cin >> p >> x[i];
        if(p == 0 )pr =i ;
        g[p].pb(i);
    }
    for(int i= 0 ; i <= n; i++){
        for(int j =0 ; j<= k ; j++)dp[i][j]  = -inf;
    }
    for(int i = 1 ; i <= n ; i++){
        dp[i][0] = 0 ;
    }
    dfs(pr , 0 );
    for(int i=1 ; i <= timer;  i++){
        for(int j = 1; j <= k ; j++){
            dp[i][j] = dp[i-1][j];
            int l = q[i].second , val = q[i].first;
            if(l==0)continue;
            dp[i][j] = max(dp[i][j] , dp[l-1][j-1]+val);
            // cout << i<< ' ' << j << ' ' << dp[i][j] << '\n';
        }
        // cout << i << ' ' << dp[i] << '\n';
    }
    cout << dp[timer][k];
}   

• Subtask 1: 60 / 100