제출 #1206825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206825		Almonther	바이오칩 (IZhO12_biochips)	C++20	10 / 100	408 ms	405148 KiB

biochips

#include"bits/stdc++.h"

using namespace std;
#define ll long long
#define co cout<<
// stuff
const int maxn=2e5+1,maxm=501;
int n,m;
vector<ll>v[maxn];
int arr[maxn];  
ll root=-1;
int values[maxn][maxm];
int mx[maxn];
void dfs(ll x,ll last){
    for(auto i:v[x]){
        if(i==last) continue;
        dfs(i,x);
        vector<pair<int,int>>added;
        for(int j=0;j<=mx[x];j++){
            for(int k=1;k<=mx[i]&&j+k<=m;k++){
                if(values[x][j]+values[i][k]>values[x][j+k]) added.push_back({j,k});
            }
        }
        for(auto [i1,j1]:added){
            values[x][i1+j1]=max(values[x][i1+j1],values[x][i1]+values[i][j1]);
            mx[x]=max(mx[x],i1+j1);
            mx[x]=min(mx[x],m);
        }
    }
    values[x][1]=max(values[x][1],arr[x]);
    mx[x]=max(mx[x],1);
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ll a;
        cin>>a>>arr[i];
        if(a==0){
            root=i;
            continue;
        }
        v[i].push_back(a);
        v[a].push_back(i);
    }
    dfs(root,-1);
    co values[root][m-1];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

• Subtask 1: 10 / 100