Submission #1037027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037027		pera	Biochips (IZhO12_biochips)	C++17	60 / 100	2078 ms	407692 KiB

biochips

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1 , M = 500 + 1;
int n , m , root;
vector<int> e(N);
vector<vector<int>> g(N) , dp(N , vector<int>(M));
void dfs(int u){
   //dp[u][x] MAX sum in subtree of u by choosing x chips
   for(int v : g[u]){
      dfs(v);
      for(int x = m;x >= 0;x --){
         for(int y = 0;y <= x;y ++){
            dp[u][x] = max(dp[u][x] , dp[u][y] + dp[v][x - y]);
         }
      }
   }
   dp[u][1] = max(dp[u][1] , e[u]);
   /*cout << "[ " << u << " ]: ";
   for(int x = 0;x <= m;x ++){
      cout << dp[u][x] << " ";
   }
   cout << endl;*/
}
int main(){
  cin >> n >> m;
  for(int i = 1;i <= n;i ++){
   int p;
   cin >> p >> e[i];
   if(p > 0){
      g[p].push_back(i);
   }else{
      root = i;
   }
  }
  dfs(root);
  cout << dp[root][m] << endl;
}

• Subtask 1: 60 / 100