oj.uz

답안 #352335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
352335 2021-01-20T15:41:15 Z rqi 바이오칩 (IZhO12_biochips) C++14
100 / 100
 600 ms 21484 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second
#define mp make_pair

#define sz(x) (int)(x).size()

const int mx = 200005;
int N, M;
vi children[mx];
int x[mx];
vi dp[mx];

void genDP(int node){
	dp[node] = vi{0};
	for(auto u: children[node]){
		genDP(u);

		vi res = vi(min(M+1, sz(dp[node])+sz(dp[u])-1), 0);
		for(int i = 0; i < sz(dp[node]); i++){
			for(int j = 0; j < min(M+1-i, sz(dp[u])); j++){
				res[i+j] = max(res[i+j], dp[node][i]+dp[u][j]);
			}
		}
		dp[node] = res;
	}

	if(sz(dp[node]) < 2){
		dp[node].pb(0);
	}

	dp[node][1] = max(dp[node][1], x[node]);
}

int main(){
	cin >> N >> M;

	for(int i = 1; i <= N; i++){
		int p;
		cin >> p >> x[i];
		children[p].pb(i);
	}

	genDP(0);

	cout << dp[0][M] << "\n";
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 14 ms 10348 KB Output is correct
5 Correct 16 ms 10348 KB Output is correct
6 Correct 15 ms 10348 KB Output is correct
7 Correct 278 ms 18284 KB Output is correct
8 Correct 273 ms 18028 KB Output is correct
9 Correct 464 ms 20460 KB Output is correct
10 Correct 600 ms 21484 KB Output is correct