oj.uz

Submission #1111671

# Submission time Handle Problem Language Result Execution time Memory
1111671 2024-11-12T14:33:10 Z 0pt1mus23 Dostavljač (COCI18_dostavljac) C++14
140 / 140
 3 ms 4696 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3064 KB Output is correct
2 Correct 1 ms 2896 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 3 ms 3664 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3664 KB Output is correct
2 Correct 3 ms 3664 KB Output is correct