oj.uz

답안 #1037037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037037 2024-07-27T22:44:12 Z pera 바이오칩 (IZhO12_biochips) C++17
100 / 100
 480 ms 487456 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100 , M = 500 + 100;
int n , m , root , T = 0;
vector<int> e(N) , in(N) , out(N) , ord = {0};
vector<vector<int>> g(N) , dp(N , vector<int>(M));
void dfs(int u){
   in[u] = ++T;
   ord.push_back(u);
   for(int v : g[u]){
      dfs(v);
   }
   out[u] = T;
}
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);
  for(int i = 0;i < N;i ++){
     for(int j = 0;j < M;j ++){
        dp[i][j] = -1e9;
     }
  }
  dp[n + 1][0] = 0;
  for(int i = n;i >= 1;i --){
     dp[i][0] = 0;
     for(int x = 1;x <= m;x ++){
        dp[i][x] = max(dp[i + 1][x] , dp[out[ord[i]] + 1][x - 1] + e[ord[i]]);
     }
  }
  cout << dp[1][m] << endl;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 485200 KB Output is correct
2 Correct 297 ms 485184 KB Output is correct
3 Correct 302 ms 485200 KB Output is correct
4 Correct 290 ms 485456 KB Output is correct
5 Correct 287 ms 485200 KB Output is correct
6 Correct 278 ms 485440 KB Output is correct
7 Correct 392 ms 487372 KB Output is correct
8 Correct 415 ms 487432 KB Output is correct
9 Correct 423 ms 487456 KB Output is correct
10 Correct 480 ms 487440 KB Output is correct