結果

問題 No.417 チューリップバブル
ユーザー btkbtk
提出日時 2016-08-27 00:37:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 1,485 bytes
コンパイル時間 1,873 ms
コンパイル使用メモリ 171,312 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-26 04:59:01
合計ジャッジ時間 3,801 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,816 KB
testcase_01 AC 4 ms
6,944 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 4 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 5 ms
6,944 KB
testcase_07 AC 4 ms
6,940 KB
testcase_08 AC 7 ms
6,940 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 13 ms
6,944 KB
testcase_11 AC 13 ms
6,944 KB
testcase_12 AC 12 ms
6,940 KB
testcase_13 AC 20 ms
6,944 KB
testcase_14 AC 20 ms
6,940 KB
testcase_15 AC 21 ms
6,940 KB
testcase_16 AC 21 ms
6,940 KB
testcase_17 AC 40 ms
6,940 KB
testcase_18 AC 41 ms
6,940 KB
testcase_19 AC 41 ms
6,940 KB
testcase_20 AC 40 ms
6,940 KB
testcase_21 AC 40 ms
6,940 KB
testcase_22 AC 40 ms
6,944 KB
testcase_23 AC 41 ms
6,940 KB
testcase_24 AC 41 ms
6,944 KB
testcase_25 AC 40 ms
6,940 KB
testcase_26 AC 29 ms
6,940 KB
testcase_27 AC 28 ms
6,944 KB
testcase_28 AC 41 ms
6,940 KB
testcase_29 AC 39 ms
6,940 KB
testcase_30 AC 40 ms
6,944 KB
testcase_31 AC 40 ms
6,944 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 3 ms
6,944 KB
testcase_34 AC 9 ms
6,944 KB
testcase_35 AC 81 ms
6,944 KB
testcase_36 AC 80 ms
6,940 KB
testcase_37 AC 81 ms
6,940 KB
testcase_38 AC 82 ms
6,940 KB
testcase_39 AC 82 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct I{
    I(){
        ios::sync_with_stdio(false);cin.tie(0);
    }
}init;

typedef vector<int> V;
typedef vector<V> Graph;/*木を構築 Gは木じゃないとだめ*/
/*G:元の隣接リスト P:空の親ノード表 C:空の子ノード隣接リスト*/
void make_tree(int v, Graph &G,Graph &cost, int p, Graph &C,Graph &cc) {
    for (int i=0;i<G[v].size();i++) {
        int e=G[v][i];
        int ccc=cost[v][i];
        if (e != p) {
            C[v].push_back(e);
            cc[v].push_back(ccc);
            make_tree(e, G, cost,v, C,cc);
	}
    }
}

V dfs(int v,Graph& G,Graph &cost,V& U){
    V dp(1001,0);
    dp[0]=U[v];
    for(int id=0;id<G[v].size();id++){
        auto u=G[v][id];
        auto c=cost[v][id];
        auto v=dfs(u,G,cost,U);
        V nxt=dp;
        for(int i=c;i<=1000;i++)
            for(int j=0;i+j<=1000;j++){
                nxt[i+j]=max(nxt[i+j],dp[j]+v[i-c]);
            }
        swap(dp,nxt);
    }
    return dp;
}

int main(){
    int N,M;cin>>N>>M;
    V U(N);
    for(auto &v:U)cin>>v;
    Graph g(N),tree(N),cost(N),cww(N);
    for(int i=1;i<N;i++){
        int A,B,C;
        cin>>A>>B>>C;
        g[A].push_back(B);
        cww[A].push_back(C);
        
        g[B].push_back(A);
        cww[B].push_back(C);
    }
    make_tree(0,g,cww,0,tree,cost);
    V dp=dfs(0,tree,cost,U);
    int res=0;
    for(int i=0;i<=M/2;i++)res=max(res,dp[i]);
    cout<<res<<endl;
    return 0;
}
0