제출 #717290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717290		Ahmed57	Dostavljač (COCI18_dostavljac)	C++14	140 / 140	280 ms	4292 KiB

dostavljac

#include <bits/stdc++.h>

using namespace std;
long long dp[2][501][501];
long long n,m;
vector<int> adj[501];
int arr[501];
void dfs(int i,int pr){
    for(int j = 1;j<=m;j++)dp[0][i][j] = arr[i],dp[1][i][j] = arr[i];
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
        for(int k = m;k>=1;k--){
            for(int c = 1;c<k;c++){
                dp[0][i][k] = max(dp[0][i][k],dp[0][j][c]+dp[1][i][k-(c+1)]);
                if(k>c+1)dp[0][i][k] = max(dp[0][i][k],dp[1][j][c]+dp[0][i][k-(c+2)]);
                if(k>c+1)dp[1][i][k] = max(dp[1][i][k],dp[1][j][c]+dp[1][i][k-(c+2)]);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>arr[i];
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    cout<<max(dp[0][1][m],dp[1][1][m])<<endl;
}

• 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