Submission #685243

#	Time	Username	Problem	Language	Result	Execution time	Memory
685243		Ronin13	Biochips (IZhO12_biochips)	C++14	100 / 100	567 ms	397144 KiB

biochips

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 2e5 + 1;
vector <vector <int> > g(nmax);
int dp[nmax][501];
vector <int> a(nmax);
int ans = 0;
int last;
int m;
void dfs(int v, int e = -1){
    for(int j=  500; j >= 1; j--){
            dp[v][j] = max(dp[v][j], dp[last][j - 1] + a[v]);
            dp[v][j] = max(dp[v][j], dp[last][j]);
    }
    ans = max(ans, dp[v][m]);
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    for(int j = 500; j >= 1; j--){
        dp[v][j] = max(dp[v][j], dp[last][j]);
    }
    last = v;
}

int main(){
    int n; cin >> n;
    cin >> m;
    int root = 0;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        g[x].pb(i);
        if(!x) root = i;
        cin >> a[i];
    }
    for(int i = 1; i <= 500; i++)
        dp[0][i] = -1e9;
    dfs(root);
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100