Submission #48494

#TimeUsernameProblemLanguageResultExecution timeMemory
48494aleksamiDostavljač (COCI18_dostavljac)C++14
14 / 140
1048 ms2612 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 505 int n,m; int a[MAXN]; int dp[MAXN][MAXN][2]; int dpp[MAXN][2]; 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 = 0; i <= m; i++) { //dp[v][i][0]=max(dp[v][i][0],dpp[i][0]); //dp[v][i][1]=max(dp[v][i][1],dpp[i][1]); //dp[v][i][0]=max(dp[v][i][0],dp[v][i][1]); dpp[i][0]=0; dpp[i][1]=0; } for(int i = 0; i <= m; i++) { for(int j = 0; j <= m; j++) { if(i>0)dpp[i][0]=max(dpp[i][0],dpp[i-1][0]); if(i>0)dpp[i][1]=max(dpp[i][1],dpp[i-1][1]); dpp[i][0]=max(dpp[i][0],dpp[i][1]); dpp[i][0]=max(dpp[i][0],dp[v][i][0]); if(i-j-1>=0)dpp[i][0]=max(dpp[i][0],dp[v][j][1]+dp[x][i-j-1][0]); dpp[i][1]=max(dpp[i][1],dp[v][i][1]); if(i-j-2>=0)dpp[i][1]=max(dpp[i][1],dp[v][j][1]+dp[x][i-j-2][1]); if(j-2>=0&&i-j>=0)dpp[i][1]=max(dpp[i][1],dp[v][j-2][1]+dp[x][i-j][1]); } } for(int i = 0; i <= m; i++) { dp[v][i][0]=max(dp[v][i][0],dpp[i][0]); dp[v][i][1]=max(dp[v][i][1],dpp[i][1]); dp[v][i][0]=max(dp[v][i][0],dp[v][i][1]); dpp[i][0]=0; dpp[i][1]=0; } } for(int i = m; i >= 1; i--) { if(i>0)dp[v][i][0]=max(dp[v][i][0],dp[v][i-1][0]+a[v]); if(i>0)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]); } for(int i = 1; i <= m; i++) { dp[v][i][0]=max(dp[v][i][0],dp[v][i-1][0]); dp[v][i][1]=max(dp[v][i][1],dp[v][i-1][1]); dp[v][i][0]=max(dp[v][i][0],dp[v][i][1]); } } 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); cout << max(dp[1][m][0],dp[1][m][1]); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { // cout << dp[i][j][0] << " "; } } 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...