Submission #1207033

#TimeUsernameProblemLanguageResultExecution timeMemory
1207033em4ma2Biochips (IZhO12_biochips)C++20
100 / 100
517 ms401172 KiB
// اللهم صل على محمد وعلى ال محمد كما صليت على ابراهيم وعلى ال ابراهيم انك حميد مجيد #include "bits/stdc++.h" using namespace std; #define ll long long //#define int long long #define pb push_back #define applejuice ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); const int mod=1e9+7; const int inf=1e9; const int mxsz=2e5+4; const int off=1<<20; const int siz=504; vector<int>adj[mxsz]; int vis[mxsz]; int a[mxsz]; int dp[mxsz][siz]; int sz[mxsz]; void dfs(int i){ vis[i]=1; for (auto x:adj[i]){ if (!vis[x]){ dfs(x); sz[i]+=sz[x]; } } } void tra(int i,int m){ vis[i]=1; for (auto x:adj[i]) { if (!vis[x])tra(x,m); //cout<<"sdj;"; for (int j = m; j >=0; j--) { for (int l = min(sz[x],j); l >=0; l--) { dp[i][j]=max(dp[i][j],dp[x][l]+dp[i][j-l]); } } } dp[i][1]=max(dp[i][1],a[i]); } signed main(){ applejuice; int n,m; cin>>n>>m; int root; for (int i=1;i<=n;i++){ int p, x; cin>>p>>x; a[i]=x; if (p==0)root=i; adj[p].pb(i); } for (int i=0;i<=n;i++){ for (int j=0;j<=m;j++){ dp[i][j]=-inf; } } for (int i=0;i<=n;i++){ dp[i][0]=0; } /*for (int i=1;i<=n;i++){ if (adj[i].size()==0){ dp[i][1]=a[i]; } }*/ for (int i=1;i<=n;i++){ sz[i]=1; } dfs(root); for (int i=0;i<=n;i++)vis[i]=0; tra(root,m); /*for (int i=1;i<n;i++){ for (int j=1;j<=m;j++){ cout<<dp[i][j]<<" "; } }*/ cout<<dp[root][m]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...