Submission #481389

#	Time	Username	Problem	Language	Result	Execution time	Memory
481389		Edbert2397	Biochips (IZhO12_biochips)	C++14	0 / 100	186 ms	524292 KiB

biochips

# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
#define pii pair<int,int>
#define debug(x) cout << #x << '=' << x << endl;
const int N = 2e5 + 5;
const int INF = 1e9;
const ll mod = 1e9+7;
int n,m,x[N],now,sz,dp[N][505],z,nilai[N][505];
vector<int>v[N],urutan;
void dfs(int idx){
    for(auto isi : v[idx]){
        dfs(isi);
    }
    urutan.pb(idx);
}
int f(int idx,int sisa){
    if(sisa == 0) return 0;
    if(idx == sz) return -INF;
    if(idx >= 0 && dp[v[now][idx]][sisa] != -1) return dp[v[now][idx]][sisa];
    int res = f(idx + 1,sisa);
    for(int i = 1;i<=m;i++){
        if(i > sisa) break;
        if(nilai[v[now][idx]][i] == -1) break;
        res = max(res,f(idx + 1,sisa - i) + nilai[v[now][idx]][i]);
    }
    if(idx == -1) return res;
    return dp[v[now][idx]][sisa] = res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(,r,stdin);
    //freopen(,w,stdout);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        int p;
        cin>>p>>x[i];
        v[p].pb(i);
    }
    dfs(0);
    memset(dp,-1,sizeof(dp));
    memset(nilai,-1,sizeof(nilai));
    for(auto isi : urutan){
        now = isi;
        sz = v[isi].size();
        for(int i = 1;i<=min((int)v[isi].size(),m);i++){
            z = i;
            nilai[isi][i] = f(-1,i);
        }
        nilai[isi][1] = max(nilai[isi][1],x[isi]); 
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        ans =max(ans,nilai[i][m]);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 100