Submission #843226

#	Time	Username	Problem	Language	Result	Execution time	Memory
843226		dungz	Biochips (IZhO12_biochips)	C++17	100 / 100	206 ms	403476 KiB

biochips

//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<int> a[200005];
int in[200005],out[200005];
int d=0;
int f[200005][505];
int val[200005];
void dfs(int u,int par)
{
    in[++d]=u;
    for(auto i:a[u])
    {
        if(i!=par)
        {
            dfs(i,u);
        }
    }
    out[u]=d;
}
int main(){
//    #ifndef ONLINE_JUDGE
//           freopen (task".inp", "r", stdin);
//           freopen (task".out", "w", stdout);
//    #endif
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(i);
//        cout<<x<<" "<<i<<endl;
        val[i]=y;

    }
    dfs(0,-1);
    for(int i=1;i<=d+1;i++) for(int j=1;j<=m;j++) f[i][j]=-2e9;
//    for(int i=1;i<=d;i++) cout<<in[i]<<" ";
//    cout<<endl;
    for(int i=d;i>=2;i--)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(val[in[i]]+f[out[in[i]]+1][j-1],f[i+1][j]);
//            ans=max(ans,f[i][j]);
        }
    }
    cout<<f[2][m];
}
/*
o(n*m^2) done

*/

• Subtask 1: 100 / 100