Submission #1021441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021441		Minbaev	Biochips (IZhO12_biochips)	C++17	100 / 100	419 ms	398160 KiB

biochips

//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,dp[200001][501],res,timer=1,root;
struct node{
    int l,r,cost;
};
node a[200001];
vector<int>g[200001];
void dfs(int v){
    if(g[v].empty())timer++;
    a[v].l=timer;
    for(int to:g[v])dfs(to);
    a[v].r=timer;
}
bool cmp(node l,node r){
    return l.r<r.r;
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d%d",&j,&a[i].cost);
        if(j)g[j].push_back(i);
        else root=i;
    }
    dfs(root);
    sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;i++){
        for(j=0;j<=m;j++)
            dp[a[i].r][j]=max(dp[a[i].r][j],dp[a[i].r-1][j]);
        for(j=1;j<=min(a[i].l,m);j++)if(a[i].l != 1)dp[a[i].r][j]=max(dp[a[i].r][j],dp[a[i].l-(a[i].l==a[i].r)][j-1]+a[i].cost);
    }
    for(i=1;i<=timer;i++)res=max(res,dp[i][m]);
    if(m == 1){
		for(int i = 1;i<=n;i++){
			if(a[i].l == 1)res = max(res, a[i].cost);
		}
	}
    printf("%d",res);
    //~ cout << "\n";
    //~ for(int i = 1;i<=n;i++){
		//~ cout << a[i].cost << " " << a[i].l << " " << a[i].r << "\n";
	//~ }
    
    
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
biochips.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d",&j,&a[i].cost);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100