oj.uz

Submission #519345

# Submission time Handle Problem Language Result Execution time Memory
519345 2022-01-26T08:32:29 Z FireGhost1301 Biochips (IZhO12_biochips) C++11
100 / 100
 465 ms 412556 KB 
// 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9848 KB Output is correct
4 Correct 15 ms 27596 KB Output is correct
5 Correct 17 ms 29892 KB Output is correct
6 Correct 18 ms 29900 KB Output is correct
7 Correct 279 ms 308892 KB Output is correct
8 Correct 283 ms 308904 KB Output is correct
9 Correct 334 ms 374204 KB Output is correct
10 Correct 465 ms 412556 KB Output is correct