oj.uz

Submission #1037027

# Submission time Handle Problem Language Result Execution time Memory
1037027 2024-07-27T22:32:14 Z pera Biochips (IZhO12_biochips) C++17
60 / 100
 2000 ms 407692 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 405072 KB Output is correct
2 Correct 242 ms 405332 KB Output is correct
3 Correct 239 ms 405096 KB Output is correct
4 Correct 254 ms 405328 KB Output is correct
5 Correct 244 ms 405332 KB Output is correct
6 Correct 278 ms 405332 KB Output is correct
7 Execution timed out 2054 ms 407632 KB Time limit exceeded
8 Execution timed out 2078 ms 407692 KB Time limit exceeded
9 Execution timed out 2051 ms 407376 KB Time limit exceeded
10 Execution timed out 2071 ms 407560 KB Time limit exceeded