oj.uz

Submission #173486

# Submission time Handle Problem Language Result Execution time Memory
173486 2020-01-04T09:09:13 Z juggernaut Biochips (IZhO12_biochips) C++14
0 / 100
 7 ms 5144 KB 
//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]),dp[a[i].r][j]=max(dp[a[i].r][j],dp[a[i].l-1][j-1]+a[i].cost);
    }
    for(i=1;i<=timer;i++)res=max(res,dp[i][m]);
    printf("%d",res);
}

Compilation message

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]
     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]
         scanf("%d%d",&j,&a[i].cost);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Incorrect 7 ms 5144 KB Output isn't correct
4 Halted 0 ms 0 KB -