Submission #16857

#	Time	Username	Problem	Language	Result	Execution time	Memory
16857		hasanb	Biochips (IZhO12_biochips)	C++98	100 / 100	255 ms	479364 KiB

biochips

#include<bits/stdc++.h>

using namespace std;
#define FORR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define ll long long
#define pii pair<int,int>
#define mod 1000000007
#define N (int)(2e5+10)
#define mp make_pair
#define pb push_back
#define sd second
#define ft first
#define endll puts("")
#define endl '\n'
#define inf mod
int n,m,root,val[N],dp[N][600],a,FT[N],ST[N],T,w[N];
vector<int>V[N];
void dfs(int x){
   ST[x] = ++T;
   w[T] = x;
   FOR(i,0,(int)V[x].size()-1)
      dfs(V[x][i]);
   FT[x] = T;
}
int main(){
   cin >> n >> m;
   FOR(i,1,n){
      scanf("%d %d",&a,&val[i]);
      if(!a) root = i;
      V[a].pb(i);
   }
   dfs(root);

   FOR(i,0,m)
      dp[n+1][i] = -inf;

   dp[n+1][0] = 0;
   
   ROF(i,n,1)
      FOR(j,0,m)
         dp[i][j] = max(dp[i+1][j] , (j!=0) * (val[w[i]] + dp[FT[w[i]]+1][j-1]));

   cout << dp[1][m] << endl;
}

• Subtask 1: 100 / 100