Submission #49914

#	Time	Username	Problem	Language	Result	Execution time	Memory
49914		mra2322001	Biochips (IZhO12_biochips)	C++14	0 / 100	2053 ms	210952 KiB

biochips

#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 (stderr)

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