Submission #716555

#	Time	Username	Problem	Language	Result	Execution time	Memory
716555		vjudge1	Biochips (IZhO12_biochips)	C++17	0 / 100	71 ms	19404 KiB

biochips

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
struct segment{int l, r, id;
int size(){return r-l+1;}};
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 25e4 + 100;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n, m;
int a[maxn];
ll dp[10001][101];
vector<int> g[maxn];

void dfs(int v){
    fill(dp[v] + 1, dp[v] + m + 1, -inf);
    for(int to: g[v]){
        dfs(to);
        for(int x = 0; x <= m; x++){
            for(int y = 0; y <= x; y++){
                dp[v][x] = max(dp[v][x], dp[v][x - y] + dp[to][y]);
            }
        }
    }
    dp[v][1] = max(dp[v][1], 1ll * a[v]);
}

void test(){
    cin >> n >> m; int r;
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p >> a[i];
        if(p == 0){
            r = i;
            continue;
        }
        g[p].push_back(i);
    }
    dfs(r);
    cout << dp[r][m];
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

Compilation message (stderr)

biochips.cpp: In function 'void test()':
biochips.cpp:55:20: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     cout << dp[r][m];
      |                    ^

• Subtask 1: 0 / 100