Submission #469010

#	Time	Username	Problem	Language	Result	Execution time	Memory
469010		wdjpng	Chase (CEOI17_chase)	C++17	70 / 100	2359 ms	94740 KiB

chase

    #include <bits/stdc++.h>
     
    #pragma GCC optimize ("O3")
    #pragma GCC optimize ("unroll-loops")
     
    #define int long long
    #define rep(i,n) for(int i = 0; i < n; i++)
     
    using namespace std;
     
    int n,v;
    vector<int>p;
    vector<vector<int>>mem;
    vector<vector<int>>E;
     
    int dfs(int pos, int bc, int parent)
    {
        if(mem[pos][bc]!=-1) return mem[pos][bc];
        if(bc==0) return 0;
        
        int sum = 0;
        for(int w : E[pos])
        {
            if(w==parent) continue;
            sum+=p[w];
        }
     
        int maxx = 0;
        for(int w : E[pos])
        {
            if(w==parent) continue;
            if(parent!=-1) maxx=max(maxx, dfs(w, bc, pos));
            maxx=max(maxx, dfs(w, bc-1, pos) + sum);
        }
     
        return mem[pos][bc] = maxx;
    }
     
    int bruteforce()
    {
        int maxx=0;
        rep(i, n) 
        {
            mem.assign(n+1, vector<int>(v+1, -1));
            maxx=max(maxx, dfs(i+1, v, -1));
        }
        return maxx;
    }
     
    signed main()
    {
        cin>>n>>v;
        p.resize(n+1);
        rep(i, n) cin>>p[i+1];
     
        E.resize(n+1);
        mem.assign(n+1, vector<int>(v+1, -1));
     
        rep(i,n-1)
        {
            int a,b;
            cin>>a>>b;
            E[a].push_back(b);
            E[b].push_back(a);
        }
        int maxx = dfs(1, v, -1);
        if(n<=1000) maxx = bruteforce();
        cout<<maxx<<"\n";
    }

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30