Submission #197763

#TimeUsernameProblemLanguageResultExecution timeMemory
197763heonDostavljač (COCI18_dostavljac)C++17
14 / 140
1730 ms60508 KiB
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <queue> #include <bitset> #include <stack> #include <iomanip> using namespace std; #define all(x) x.begin(), x.end() typedef vector <int> vi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; const int mod = 1e9 + 7; const ll inf = 3e18 + 5; int add(int a, int b) { return (a += b) < mod ? a : a - mod; } int mul(int a, int b) { return 1LL * a * b % mod; } int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; } int ctz(int x) { return __builtin_ctz(x); } int clz(int x) { return __builtin_clz(x); } vi g[505]; int dp[505][505][30][2]; int a[505]; int dfs(int u, int m, int c, int took, int p){ if(m < 0) return -mod; if(c == int(g[u].size())){ if(m && !took) return a[u]; return 0; } int& ret = dp[u][m][c][took]; if(ret != -1) return ret; ret = 0; if(g[u][c] == p) return ret = dfs(u, m, c + 1, took, p); if(!took) ret = max(ret, a[u] + dfs(u, m - 1, c, 1, p)); ret = max(ret, dfs(g[u][c], m - 1, 0, 0, u)); ret = max(ret, dfs(u, m, c + 1, took, p)); for(int i = 0; i <= m - 2; i++){ ret = max(ret, dfs(g[u][c], i, 0, 0, u) + dfs(u, m - 2 - i, c + 1, took, p)); } return ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n, t; cin >> n >> t; 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); } memset(dp, -1, sizeof dp); cout << dfs(1, t, 0, 0, 1); }
#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...