Submission #519345

#	Time	Username	Problem	Language	Result	Execution time	Memory
519345		FireGhost1301	Biochips (IZhO12_biochips)	C++11	100 / 100	465 ms	412556 KiB

biochips

// https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 3, M = 500 + 3;
int n, m, a[N];
vector<int> g[N];
int id, in[N], out[N];
vector<int> lst[N];
int f[N][M];

void dfs(int u) {
    in[u] = ++id;
    for (int v: g[u]) dfs(v);
    out[u] = id;
    lst[id].push_back(u);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int p; cin >> p >> a[i];
        g[p].push_back(i);
    }
    dfs(g[0][0]);
    for (int i = 1; i <= m; ++i) f[0][i] = -1e9;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            f[i][j] = f[i - 1][j];
            for (int x: lst[i]) f[i][j] = max(f[i][j], f[in[x] - 1][j - 1] + a[x]);
        }
    }
    cout << f[n][m];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 100 / 100