Submission #519525

#	Time	Username	Problem	Language	Result	Execution time	Memory
519525		Minhho	Biochips (IZhO12_biochips)	C++17	100 / 100	302 ms	400140 KiB

biochips

#define taskname "BIOCHIP"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 1;
vector<int> adj[maxn];
int v[maxn], a[maxn], out[maxn], n, m, root, tme = 1;
int dp[maxn][501];
/**
 * a[i] = x: the value at time i is equal to x
 * out[i] = t: at the exit time i, enter time is t
 * dp[i][j]: choose j segments at exit time i
**/
void DFS(int u)
{
    int t = tme;
    for (int v: adj[u]) DFS(v);
    a[tme] = v[u];
    out[tme++] = t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    cin>>n>>m;
    for (int i=1, x; i<=n; i++)
    {
        cin>>x>>v[i];
        adj[x].emplace_back(i);
    }
    DFS(0);
    for (int i=0; i<=n; i++) for (int j=1; j<=m; j++) dp[i][j] = -1e9;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            dp[i][j] = max(dp[i-1][j], dp[out[i]-1][j-1] + a[i]);

    cout<<dp[n][m];
}

• Subtask 1: 100 / 100