Submission #994398

#TimeUsernameProblemLanguageResultExecution timeMemory
994398LOLOLOBiochips (IZhO12_biochips)C++17
10 / 100
264 ms399880 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e5 + 10; vector <int> ed[N]; int sz[N], a[N]; int f[N][501]; int n, m; void dfs(int u) { f[u][0] = 0; sz[u] = 1; for (auto x : ed[u]) { dfs(x); sz[u] += sz[x]; for (int i = min(sz[u], m); i >= max(1, sz[u] - sz[x] - m); i--) { for (int j = 0; j <= sz[x] && j <= i; j++) { if (f[x][j] == -1) continue; f[u][i] = max(f[u][i], f[x][j] + f[u][i - j]); } } } f[u][1] = max(f[u][1], a[u]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); mem(f, -1); cin >> n >> m; int root = 0; for (int i = 1; i <= n; i++) { int x; cin >> x >> a[i]; if (x) { ed[x].pb(i); } else { root = i; } } dfs(root); cout << f[root][m] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...