oj.uz

Submission #519525

# Submission time Handle Problem Language Result Execution time Memory
519525 2022-01-26T14:17:22 Z Minhho Biochips (IZhO12_biochips) C++17
100 / 100
 302 ms 400140 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 14 ms 22772 KB Output is correct
5 Correct 19 ms 24900 KB Output is correct
6 Correct 15 ms 24888 KB Output is correct
7 Correct 250 ms 298488 KB Output is correct
8 Correct 215 ms 298512 KB Output is correct
9 Correct 268 ms 362408 KB Output is correct
10 Correct 302 ms 400140 KB Output is correct