# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
524150 | Gurban | Biochips (IZhO12_biochips) | C++17 | 3 ms | 4940 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=2e5+1;
const int N = 501;
int n,m,a[maxn];
int rgt[maxn];
vector<int>E[maxn],v;
void dfs(int nd){
v.push_back(nd);
for(auto i : E[nd]) dfs(i);
rgt[nd] = (int)v.size() - 1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int root = 1;
for(int i = 1;i < n;i++){
int p; cin >> p >> a[i];
if(!p) root = i;
E[p].push_back(i);
}
dfs(root);
// for(auto i : v) cout<<i<<' ';
// cout<<'\n';
vector<vector<int>>dp((int)v.size() + 1,vector<int>(m + 1,-1e9));
dp[(int)v.size()][0] = 0;
int ans = -1e9;
for(int i = (int)v.size()-1;i >= 0;i--){
for(int j = 1;j <= m;j++){
dp[i][j] = dp[rgt[v[i]] + 1][j - 1] + a[v[i]];
dp[i][j] = max(dp[i][j],dp[i + 1][j]);
}
ans = max(ans,dp[i][m]);
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |