Submission #48462

#TimeUsernameProblemLanguageResultExecution timeMemory
48462aleksamiDostavljač (COCI18_dostavljac)C++14
0 / 140
198 ms2476 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 505 int n,m; int dp[MAXN][MAXN][2]; int a[MAXN]; vector <int> g[MAXN]; void dfs(int v,int p) { for(auto x:g[v]) { if(x==p)continue; dfs(x,v); for(int i = m; i >= 0; i--) { dp[v][i][0]=max(dp[v][i+1][0],dp[v][i][0]); dp[v][i][1]=max(dp[v][i+1][1],dp[v][i][1]); for(int j = i; j >= 0; j--) { if(i-j-1>=0)dp[v][i][0]=max(dp[v][i][0],dp[v][j][1]+dp[x][i-j-1][0]); if(i-j-2>=0)dp[v][i][1]=max(dp[v][i][1],dp[v][j][1]+dp[x][i-j-2][1]); } dp[v][i][0]=max(dp[v][i][0],dp[v][i][1]); } } for(int i = m; i >= 1; i--) { dp[v][i][0]=max(dp[v][i][0],dp[v][i-1][0]+a[v]); dp[v][i][1]=max(dp[v][i][1],dp[v][i-1][1]+a[v]); dp[v][i][0]=max(dp[v][i][0],dp[v][i][1]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 0; i < n-1; i++) { int u,v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); cout << max(dp[1][m][0],dp[1][m][1]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...