제출 #1206887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206887		mohyay	Biochips (IZhO12_biochips)	C++20	60 / 100	2109 ms	475436 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define endl '\n'
using ll = int;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
const ll mod = 998244353;
ll dp[212345][600], a[212345], sz[212345];
vector<ll> v[212345];
ll m;
void dfs(ll i, ll p) {
    dp[i][0] = 0;
    for (auto j : v[i]) {
        if (j != p) dfs(j, i);
        for (ll k = min(sz[i],m); k >= 0; k--) {
            for (ll k1 = k; k1 >= 0; k1--) {
                dp[i][k] = max(dp[i][k], dp[i][k1] + dp[j][abs(k-k1)]);
            }
        }
    }
    dp[i][1] = max(dp[i][1], a[i]);
}
void dfssz(ll i, ll p) {
    sz[i] = 1;
    for (auto j : v[i]) {
        if (j != p) dfssz(j, i);
        sz[i] += sz[j];
    }
}
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    ll n; cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j = 0; j<=m; j++) dp[i][j] = -INT_MAX;
    ll root;
    for (int i=1; i<=n; i++) {
        ll p, x;
        cin>>p>>x;
        v[p].pb(i);
        a[i] = x;
        if (p == 0) root = i;
    }
    dfssz(root, 0);
    dfs(root, 0);
    cout << dp[root][m];
}

• Subtask 1: 60 / 100