Submission #49900

# Submission time Handle Problem Language Result Execution time Memory
49900 2018-06-04T13:56:18 Z mra2322001 Biochips (IZhO12_biochips) C++14
0 / 100
2 ms 128 KB
#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 200002;
const int M = 502;

int f[N][M], n, m, cost[N], d[N][M];
vector <vector <int> > a;

void dfs(int u){
    for(auto v:a[u]){
        dfs(v);
        f1(j, m) d[u][j] = f[u][j];
        f1(j, m){
            for(int k = 1; k < j; k++){
                d[u][j] = max(d[u][j], f[u][j - k] + f[v][k]);
            }
        }
        f1(j, m) d[u][j] = max(f[u][j], max(d[u][j], f[v][j]));
        f1(j, m) f[u][j] = d[u][j];
    }
    f[u][1] = max(f[u][1], cost[u]);
}

main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    a.resize(n + 1);
    int x = -1;
    memset(f, -(0x3f3f3f), sizeof(f));
    f1(i, n){
        int p, c;
        cin >> p >> cost[i];
        if(p==0){
            x = i;
        }
        else{
            a[p].push_back(i);
        }
    }
    dfs(x);
    cout << f[x][m];
}

Compilation message

biochips.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
biochips.cpp: In function 'int main()':
biochips.cpp:35:16: warning: unused variable 'c' [-Wunused-variable]
         int p, c;
                ^
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -