oj.uz

Submission #49914

# Submission time Handle Problem Language Result Execution time Memory
49914 2018-06-05T00:38:47 Z mra2322001 Biochips (IZhO12_biochips) C++14
0 / 100
 2000 ms 210952 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 = 100002;
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:36:16: warning: unused variable 'c' [-Wunused-variable]
         int p, c;
                ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 196856 KB Output is correct
2 Correct 151 ms 196916 KB Output is correct
3 Correct 146 ms 196952 KB Output is correct
4 Correct 187 ms 210952 KB Output is correct
5 Correct 199 ms 210952 KB Output is correct
6 Correct 222 ms 210952 KB Output is correct
7 Execution timed out 2053 ms 210952 KB Time limit exceeded
8 Halted 0 ms 0 KB -