oj.uz

Submission #85266

# Submission time Handle Problem Language Result Execution time Memory
85266 2018-11-19T02:19:36 Z zoooma13 Biochips (IZhO12_biochips) C++14
100 / 100
 493 ms 7160 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 200005
#define MAX_M 502

int N ,M;
int A ,B;
int Mem[MAX_N];
vector <int> Adj[MAX_N];

vector <int> knap(vector<int>&a ,vector<int> b)
{
    vector <int> c(min(M+1 ,(int)(a.size()+b.size())) ,0);
    for(int i=0; i<a.size(); i++)
    for(int j=0; j<b.size() && i+j<=M; j++)
        c[i+j] = max(c[i+j] ,a[i]+b[j]);
    return c;
}
vector <int> Solve(int v)
{
    vector <int> ans = {0 ,0};
    for(int i : Adj[v])
        ans = knap(ans ,Solve(i));
    ans[1] = max(ans[1] ,Mem[v]);
    return ans;
}

int main()
{
    scanf("%d%d",&N,&M);

    int root;
    for(int i=1; i<=N; i++)
    {
        scanf("%d%d",&A,&B);

        Mem[i] = B;
        if(A == 0)
            root = i;
        else
            Adj[A].push_back(i);
    }

    printf("%d\n",Solve(root)[M]);
}

Compilation message

biochips.cpp: In function 'std::vector<int> knap(std::vector<int>&, std::vector<int>)':
biochips.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++)
                  ~^~~~~~~~~
biochips.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<b.size() && i+j<=M; j++)
                  ~^~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:31: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:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&A,&B);
         ~~~~~^~~~~~~~~~~~~~
biochips.cpp:45:24: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%d\n",Solve(root)[M]);
                   ~~~~~^~~~~~

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 5132 KB Output is correct
3 Correct 5 ms 5184 KB Output is correct
4 Correct 12 ms 5376 KB Output is correct
5 Correct 13 ms 5376 KB Output is correct
6 Correct 13 ms 5376 KB Output is correct
7 Correct 243 ms 6788 KB Output is correct
8 Correct 243 ms 6788 KB Output is correct
9 Correct 344 ms 7160 KB Output is correct
10 Correct 493 ms 7160 KB Output is correct