oj.uz

답안 #685239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685239 2023-01-23T17:53:31 Z Ronin13 바이오칩 (IZhO12_biochips) C++14
10 / 100
 478 ms 397032 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 2e5 + 1;
vector <vector <int> > g(nmax);
int dp[nmax][501];
vector <int> a(nmax);
int ans = 0;
int last;
int m;
void dfs(int v, int e = -1){
    for(int j=  500; j >= 1; j--){
            dp[v][j] = max(dp[v][j], dp[last][j - 1] + a[v]);
            dp[v][j] = max(dp[v][j], dp[last][j]);
    }
    ans = max(ans, dp[v][m]);
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
    }
    last = v;
}

int main(){
    int n; cin >> n;
    cin >> m;
    int root = 0;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        g[x].pb(i);
        if(!x) root = i;
        cin >> a[i];
    }
    for(int i = 1; i <= 500; i++)
        dp[0][i] = -1e9;
    dfs(root);
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5716 KB Output isn't correct
2 Correct 3 ms 5716 KB Output is correct
3 Incorrect 4 ms 5972 KB Output isn't correct
4 Incorrect 25 ms 23320 KB Output isn't correct
5 Incorrect 27 ms 25516 KB Output isn't correct
6 Incorrect 27 ms 25416 KB Output isn't correct
7 Incorrect 371 ms 296008 KB Output isn't correct
8 Incorrect 414 ms 296044 KB Output isn't correct
9 Incorrect 476 ms 359724 KB Output isn't correct
10 Incorrect 478 ms 397032 KB Output isn't correct