Submission #320984

#	Time	Username	Problem	Language	Result	Execution time	Memory
320984		Cassidy	Dostavljač (COCI18_dostavljac)	C++17	140 / 140	474 ms	3044 KiB

dostavljac

    /*  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 / 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