제출 #1224039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224039		VMaksimoski008	바이오칩 (IZhO12_biochips)	C++17	100 / 100	457 ms	398812 KiB

biochips

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<int> x(n);
  vector<vector<int>> g(n);
  int root;
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p >> x[i];
    --p;
    if (p == -1) {
      root = i;
    } else {
      g[p].push_back(i);
      g[i].push_back(p);
    }
  }
  vector<vector<int>> dp(n, vector<int>(m + 1));
  vector<int> sz(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      for (int i = min(m, sz[v]); i >= 0; i--) {
        for (int j = min(m - i, sz[u]); j >= 0; j--) {
          dp[v][i + j] = max(dp[v][i + j], dp[v][i] + dp[u][j]);          
        }
      }
      sz[v] += sz[u];
    }
    sz[v] += 1;
    dp[v][1] = max(dp[v][1], x[v]);
  };
  Dfs(root, root);
  cout << dp[root][m] << '\n';                                                               
  return 0;
}

• Subtask 1: 100 / 100