제출 #1207043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207043		ibsha	바이오칩 (IZhO12_biochips)	C++20	0 / 100	90 ms	9444 KiB

biochips

//#include <bits/stdc++.h>
#include <random>
#include "set"
#include <iostream>
#include "vector"
#include "deque"
#include "climits"
#include "algorithm"
#include "stack"
#include "map"
#include "unordered_set"
#include "bitset"
#include "queue"


/*
            ====================================================================================================
            #*###*############*####*#####*####*############*#########################################*##########
            %%%%%%%%%###%##*##=*+++=+++++++++++++*@#@%%###%%%%%%%%%%%%%%%%%%%%@%@@@%@@@@@@@@@@@@@%%%%%%%@@@%%%%#
            %%%%%%%%%%#####*##=*++++++++++++++++=*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%@@@@@@@@%%%@@%%@@@%%%%#
            %%%%%%%%%######*##=*+++++++++++++++++*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%@@@@@@@@@%%#%%%%@@%#%#%#
            %%%%%%%%%%%####*##=*++++++++++++++++=+@%@%%###%@@@%%%%%%%%%%%%%%%%%%%%%%%@@%%%%@@@@@%%@%%%%%@%%%####
            %%%%%%%%%%####%*##=*++++++++++++++++=+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@%@@@%%%%%@%######
            %%%%%%%%%%####%*##=*++++++++++++++===+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%@@@@%#@%%%%%%@%#######
            %%%%%%%%%%#####*##+++++++++++=++++=+++@%#%##%#######%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@#%%%%%%@########
            %%%%%%%%%%#####*##+*+++++++++++++++==@%%%%%@##:-%=-=-+@%%%%%%%%%%%%%%%%%%%%%%%@@%%%@@@%%%%%@%%######
            %%%%%%%%%%#####*##+*++++++++++++=+*%%%%%%%%#%*.@:-%+-++%%%%%%%%%%%%%%%%%%%@%%%@%%%%%%%%%%%@@%#######
            %%%%%%%%%%####%*##=*=++++++++++++@%%%%%%%%%%%%#@@@@@@@=-@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@#######
            %%%%%%%%%%####%*##+*++++++++++++%@%%@%%%%%%%%#%@###*#%%@@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##+*+++++++++==@@%@@@@%%@%###%#@#=%@@@@@@@#=+@%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##*++++++++++++@@@@@@%#%%%%@#@@@@@@@@@@@@@@@@@-#%%%%%%%%%%%%%%@%%%%%%%%%%@@@%%%#####
            %%%%%%%%%#########=*++++++++++@@@@@%#@@@%%@@@@@@@@@@@@@@@@@@@@%@%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%#####
            %%%%%%%%######%*##=*++++++++++@%%@@@@@@@@@%%%####%@@%%%%@@@@@@@%#%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%#####
            %%%%%%%%##########=*++++++***#%%@@@@@@%%##*++++++***#*++*#%@@@@%%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%####
            %%%%%%%%######%###=*++++++#@%%@%@@@@%#*+++++====++++++++++*#@@@@%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%###
            %%%%%%%%######%###=*++++*%%%%@@@@@@@#+++++++=========++++++*#@@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%####
            %%%%%%%%%#####%###=*++**%@#@@@@@@@@%+++=================++++*@@@@%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#########=*+*#*@%@@@@@@%@%*++*+**##*++======*####*#*%@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%%########=#+*@%@@@@@@%@@@#*+=-=****#*+=+++=**#**#*+*#%@@%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###
            %%%%%%%%%%########+#*#@@@@%%%@@@%%#*+++*+=##+#*+*++##*+%**#**#%@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%%########=#**@@@@@@@@@@@@#*+=+=+++++++*==+*#*****++*#%%@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%#########=#**@@@@@@@@@@@@#*+===++++==+=+++**++=++++#%@@@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#####%###=##%@@@@@@@@@@@@#**+========++====++==+++*#%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##
            %%%%%%%#%#########+#+%@%#@@@@@@@@@%**+========+++===*++++++#%@@@%@%%%%%%%%@%%%%@%%%%%%%%%%%%%%%%####
            %%%%%%%%%%%#######=#+@@@@@@@@@@@@@#**++===+++****#**##*+++*%%@@@@@@%%%%@@@@@@@@@@@%%%%%%%%%%%%%%####
            @%%%%%##%%########+***@@@@@@@@@@@%#***++++*****#%###%%****#%@@@@%@%%%%%%%%%%%%%%%%%%%%%%%%#%%%%%%@@@
            %%%%%%%#%##%%%%###+**##%#@@@@@@@###***+++++++++++++*******#@@@@@@%%#%%%%%%%%%%%@%%%%%%%%%%%%%%%%%##%
            #@##%%##%##%######+**+++*@%##%%%%*********+++++++**********@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##%
            %@##%#%%%####%####+#*+*+++++++++#%**************************#%#*#%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%#%%%#
            @%%###%#%########*++===========++#@*++******##########******#++======@%%%%%%%%@%%%%%%%%%%%%%%%%%#%%#
            %%%##%##%##%###*++=========+=++++++*#********######*******+*=+==--=====*%%%#%%@%%%%%%%%%%%%%%%@%%%%#
            %%%##%%#%#####+++++*+=========+==+++**#******#####*******+*+++++==:======*%#%%@%%%%%%%%%%%%%%%%%%%#%
            %%%##%%%%#++==========--=----====+++++*##*****###*****+++#*===--+=====-------+**#@@%%%%%%%%%%%%%%%%%
            %#%%%+*++==========-=--=---------========++*@********+=%#===========----------======+@%%%%%%%%%%%%%%
            %#%***++========----------------------======++@.+++++*+==========---------------=-=====@%%%%%%%%%%%%
            %%**+++=========------------=---------=======+++*+*+%++========------------------==-====%%%%%%%%%%%%
            %**++++=========--===-=--=======------===========#*++============---------====----======+*%%%%%%%%%%
            #**+++++====+============+++++========-===========+*==============--=====+++++=====+===+=+*%%%%%%%%%
            #****+++==++++=====++++++****+++++===--=========+++++++=================+++***+++++++++++++%%%%%%%%%
            #*****+++++++++++++++++***##***++===-=---=======++*=*++++==============++++**#***+++++++++*+%%%%%%%%
            #******++++***++++++***######*+=====-----=--====++*+**+++======-=--=======+*#*##***+*+****#+@@%%%%%%
            ##********+**********####%%%+++++=====-----=====++*+***+++================++*#%####*********%@%+%%%%
            ###***************######%%#**++++++=============++++*#*+++======-========++++*%%####******#*%@@%%%%%
            ####****************##%%@#***++++++++++=========+++*=**++==============++++++**%%###*********#%%*%%%
            *****************+====*%%*********+++++===+====+++++++**++==+=*=====+++++++****@##++++=+****++*@%%%%
            *************+++=====--=@************+++++++++++++++******+++++++++++++++******#*+=====+++++*+++@%%%
            ***+++++*++++++=========+########**#%%*******++******%##***+++*++++++++++*******++++====++=++++**%%%
            ***+++========++========+%######*%###%#**************%###***************########***++++++++++++**#%%
            ***+++++++=====+++====+++*@#####%%%%%%######********#######**********###%%%%##%#**#*+++++==+++++**%%
            ***++++++++=======++++++**@%#######################%*#%%%#################%%#%%##**#*+++++++++++***%
            ***+++++**+++==========+*+#%%#######################**#%%###################%@%###*##*++++*+++++***%
            ****+**+++++++=======++*#*#@%%%%%%%%###########%%%#*****##%#%###########%%%%@%%%######+++++++++++***
            #*****+++++++++=====+++***#%%%%%%%%%%%%%%%%%%%%%%**++===+*#%%%%%%%%%%%%%%%%%@@%%#######*++++===+++**
            #*****+++++++=======+++**#%%%%%%%##############*+++==-===++*####%%%%%%##%%%%@@%%%######**+=====+++**
            ##****+++++++=====+*++***#%%%%%%%###########***++++++++++=++**############%%%%%%%%####****#*+=++++**
            ====================================================================================================
*/



using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
#define _ << ' ' <<
#define clearvis for (int i=0; i<maxn;visited[i++]=false)

const ll maxn = 3e4+2, maxm = 102;

ll dp[maxn][maxm+2];
ll val[maxn];

vll edges[maxn];
bool visited[maxn];

void dfs(ll node){
    if (visited[node]) return;
    dp[node][1] = val[node];
    visited[node] = true;

    for (ll nd : edges[node]) dfs(nd);

    for (int k=1; k<=maxm; k++){
        for (int j=0; j <= k; j++) {
            for (ll nd: edges[node]) {
                dp[node][k] = max(dp[node][k], dp[node][k - j] + dp[nd][j]);
            }
        }
    }

}

void solve() {
    // cout << fixed << setprecision(6);

    ll n,m; cin >> n >> m;
    ll root;
    for (int i=1;i<=n;i++){
        ll p,x; cin >> p >> x;
        if (p == 0) root = i;
        else{
            pb(edges[p],i);
        }
        val[i] = x;
    }
    dfs(root);

    cout << dp[root][m] - dp[root][1];
}


signed main() {
    //ios::sync_with_stdio(false);cin.tie(nullptr);
    //freopen("walk.in","r",stdin);
    //freopen("walk.out","w",stdout);
    ll t=1;
    //cin >> t;
    for (int i=1; i<=t; i++){
    //    cout << "Case " << i << ":\n";
        solve();
        cout << endl;
    }


    return 0;
}

• Subtask 1: 0 / 100