Submission #1111671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111671		0pt1mus23	Dostavljač (COCI18_dostavljac)	C++14	140 / 140	3 ms	4696 KiB

dostavljac

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 5e2 +23, inf = LLONG_MAX, LG = 20;
int val[sze];
vector<int> graph[sze];
int dp[sze][sze][2];
int n,d;

int dfs(int node,int par=0){
    dp[node][1][0]=val[node];
    dp[node][1][1]=val[node];
    int sub=1;
    for(auto v:graph[node]){
        if(v!=par){
            int s2 = dfs(v,node);
            int y = min(d,sub + s2 + 2);
            for(int j= sub;j>=0;j--){
                for(int k = 0;k<=s2;k++){
                    int ns = j+k+1;
                    if(ns <= y){
                        dp[node][ns][1]=max(dp[node][ns][1],dp[node][j][0] + dp[v][k][1]);
                        ++ns;
                        if(ns<=y){
                            dp[node][ns][0]=max(dp[node][ns][0],dp[node][j][0] + dp[v][k][0]);
                            dp[node][ns][1]=max(dp[node][ns][1],dp[node][j][1] + dp[v][k][0]);
                        }
                    }
                }
            }
            sub = y;
        }
    }
    return sub;
}   

void fast(){
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>val[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dfs(1,0);
    int ans=0;
    for(int i=0;i<=d;i++){
        ans=max(ans,dp[1][i][1]);
    }
    putr(ans);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14