oj.uz

Submission #524153

# Submission time Handle Problem Language Result Execution time Memory
524153 2022-02-08T17:52:14 Z Gurban Biochips (IZhO12_biochips) C++17
100 / 100
 430 ms 394720 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=2e5+1;
const int N = 501;
int n,m,a[maxn];
int rgt[maxn];
vector<int>E[maxn],v;

void dfs(int nd){
	v.push_back(nd);
	for(auto i : E[nd]) dfs(i);
	rgt[nd] = (int)v.size() - 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	int root = 1;
	for(int i = 1;i <= n;i++){
		int p; cin >> p >> a[i];
		if(!p) root = i;
		E[p].push_back(i);
	}
	dfs(root);
	vector<vector<int>>dp((int)v.size() + 1,vector<int>(m + 1,-1e9));
	dp[(int)v.size()][0] = 0;
	int ans = -1e9;
	for(int i = (int)v.size()-1;i >= 0;i--){
		dp[i][0] = 0;
		for(int j = 1;j <= m;j++){
			dp[i][j] = dp[rgt[v[i]] + 1][j - 1] + a[v[i]];
			dp[i][j] = max(dp[i][j],dp[i + 1][j]);
		}
		ans = max(ans,dp[i][m]);
	}
	cout<<ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4972 KB Output is correct
4 Correct 7 ms 7724 KB Output is correct
5 Correct 9 ms 8616 KB Output is correct
6 Correct 10 ms 9676 KB Output is correct
7 Correct 209 ms 188272 KB Output is correct
8 Correct 215 ms 188276 KB Output is correct
9 Correct 309 ms 292788 KB Output is correct
10 Correct 430 ms 394720 KB Output is correct