oj.uz

Submission #173485

# Submission time Handle Problem Language Result Execution time Memory
173485 2020-01-04T09:07:20 Z juggernaut Biochips (IZhO12_biochips) C++14
100 / 100
 750 ms 398456 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]);
        for(j=1;j<=min(a[i].l,m);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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 22 ms 14044 KB Output is correct
5 Correct 28 ms 18552 KB Output is correct
6 Correct 29 ms 18424 KB Output is correct
7 Correct 506 ms 297516 KB Output is correct
8 Correct 507 ms 297692 KB Output is correct
9 Correct 640 ms 360580 KB Output is correct
10 Correct 750 ms 398456 KB Output is correct