Submission #48418

#TimeUsernameProblemLanguageResultExecution timeMemory
48418aleksamiDostavljač (COCI18_dostavljac)C++14
14 / 140
1022 ms4460 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 505 vector <int> g[MAXN]; int a[MAXN]; int dp[MAXN][MAXN][2][2]; int n,m; void dfs(int v,int p) { dp[v][1][1][1]=a[v]; dp[v][1][0][1]=a[v]; for(int i = 1; i <= m; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 2; k++) { dp[v][i][j][k]=max(dp[v][i][j][k],dp[v][i-1][j][k]); } } } for(auto x:g[v]) { if(x==p)continue; dfs(x,v); for(int i = m; i >= 0; i--) { for(int j = 0; j <= m; j++) { if(i-j-1>=0)dp[v][i][0][0]=max(dp[v][i][0][0],max(dp[x][i-j-1][0][0],dp[x][i-j-1][0][1])+dp[v][j][1][0]); if(i-j-1>=0)dp[v][i][0][1]=max(dp[v][i][0][1],max(dp[x][i-j-1][0][0],dp[x][i-j-1][0][1])+dp[v][j][1][1]); if(i-j-1>=0&&j>0)dp[v][i][0][1]=max(dp[v][i][0][1],max(dp[x][i-j-1][0][0],dp[x][i-j-1][0][1])+dp[v][j-1][1][0]+a[v]); if(i-j-2>=0)dp[v][i][1][0]=max(dp[v][i][1][0],max(dp[x][i-j-2][1][0],dp[x][i-j-2][1][1])+dp[v][j][1][0]); if(i-j-2>=0)dp[v][i][1][1]=max(dp[v][i][1][1],max(dp[x][i-j-2][1][0],dp[x][i-j-2][1][1])+dp[v][j][1][1]); if(j>0&&i-j-2>=0)dp[v][i][1][1]=max(dp[v][i][1][1],max(dp[x][i-j-2][1][0],dp[x][i-j-2][1][1])+dp[v][j-1][1][0]+a[v]); dp[v][i][0][1]=max(dp[v][i][0][0],dp[v][i][0][1]); dp[v][i][1][1]=max(dp[v][i][1][1],dp[v][i][1][0]); dp[v][i][0][0]=max(dp[v][i][0][0],dp[v][i][1][0]); } } for(int i = 1; i <= m; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 2; k++) { dp[v][i][j][k]=max(dp[v][i][j][k],dp[v][i-1][j][k]); dp[v][i][0][1]=max(dp[v][i][0][0],dp[v][i][0][1]); dp[v][i][1][1]=max(dp[v][i][1][1],dp[v][i][1][0]); dp[v][i][0][0]=max(dp[v][i][0][0],dp[v][i][1][0]); } } } } } int main() { 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); int mx=0; for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)mx=max(mx,dp[1][m][i][j]); cout << mx; 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...