Submission #524153

#	Time	Username	Problem	Language	Result	Execution time	Memory
524153		Gurban	Biochips (IZhO12_biochips)	C++17	100 / 100	430 ms	394720 KiB

biochips

#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 / 100