제출 #1265325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265325		phamtienhoang	Biochips (IZhO12_biochips)	C++20	100 / 100	635 ms	404952 KiB

biochips

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <stack>
#include <set>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 200002;
int f[N][502];
int a[N];
int sz[N];
int n , m;
vector<int> adj[N];
int root;

void dfs(int u , int p){
    sz[u] = 1;
    for(int i = 0 ; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(v == p)
            continue;
        dfs(v , u);
        for(int j = m ; j >= 0 ; j--){
            for(int k = min(sz[v] , j); k >= 0. ;k--){
                f[u][j] = max(f[u][j] , f[v][k] + f[u][j - k]);
            }
        }
        sz[u] += sz[v];
    }
    f[u][1] = max(f[u][1] , a[u]);

    
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n ;i++){
        int par;
        int val;
        cin >> par >> val;
        if(par == 0){
            root = i;
        }else{
            adj[i].push_back(par);
            adj[par].push_back(i);
        }
        a[i] = val;
    }
    dfs(root , -1);
    int ans = f[root][m];
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100