oj.uz

Submission #320984

# Submission time Handle Problem Language Result Execution time Memory
320984 2020-11-10T12:31:02 Z Cassidy Dostavljač (COCI18_dostavljac) C++17
140 / 140
 474 ms 3044 KB 
    /*  CF_CC_
            4U7H0R:_C4551DY */

#include <bits/stdc++.h>
#include <fstream>

using namespace std;

typedef long long ll;

#define IC ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(a,b,c) for(int a=b;a<c;a++)
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vec vector<ll>
#define fir first
#define sec second
#define pb push_back
#define mp make_pair
#define len length()
#define rev reverse
#define con continue
#define pq priority_queue <int>

const ll mx=1e5+666;
const ll mod=1e9+7;
const ll inf=1e18;
const int llg=18;

int power(ll a, ll b){
	if (b==0)
		return 1;
	ll c=power(a,b/2);
	if(b&1)
		return b*c*c;
    else
        return c*c;
}

int n,m,a[666],dp[2][666][666];
vec g[666];

void dfs(int u,int par){
    rep(i,1,m+1){
        dp[0][u][i]=a[u];
        dp[1][u][i]=a[u];
    }
    for(auto v:g[u]){
        if(v!=par){
            dfs(v,u);
            for(int i=m;i>0;i--){
                rep(j,0,i+1){
                    if(i>=j+1)
                        dp[0][u][i]=max(dp[0][u][i],max(dp[0][v][j],dp[1][v][j])+dp[1][u][i-j-1]);
                    if(i>=j+2){
                        dp[0][u][i]=max(dp[0][u][i],dp[1][v][j]+dp[0][u][i-j-2]);
                        dp[1][u][i]=max(dp[1][u][i],dp[1][v][j]+dp[1][u][i-j-2]);
                    }
                }
            }
        }
    }
}

int main(){
    IC
    cin >> n >> m;
    rep(i,1,n+1) cin >> a[i];
    rep(i,0,n-1){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    cout << max(dp[0][1][m],dp[1][1][m]);
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1132 KB Output is correct
2 Correct 69 ms 1252 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1380 KB Output is correct
2 Correct 38 ms 1380 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1892 KB Output is correct
2 Correct 279 ms 1892 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 2404 KB Output is correct
2 Correct 97 ms 2404 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 3044 KB Output is correct
2 Correct 45 ms 3044 KB Output is correct