#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
using namespace std;
const int nax = 505;
void maxi(int &a, int b) {
a = max(a, b);
}
int n, m;
int a, b;
int cost[nax];
vector <int> g[nax];
int dp[nax][nax][2][2];
int dp2[nax][2][2];
// 0 to musze wrocic -> 0
// 1 to nie musze -> 0 / 1
void dfs(int v, int p) {
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp[v][i][a][b] = -1e9;
dp[v][0][0][0] = 0;
dp[v][0][1][0] = 0;
dp[v][1][0][0] = cost[v];
dp[v][1][1][0] = cost[v];
for (auto it : g[v]) {
if (it == p) continue;
dfs(it, v);
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp2[i][a][b] = dp[v][i][a][b];
rep(i, 0, m)
rep(j, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
rep(c, 0, 1)
rep(d, 0, 1) {
if (a == 0 && b == 1) continue;
if (c == 0 && d == 1) continue;
if (a == 0 && c == 1) continue;
if (a == 1 && b == 1 && c == 1) continue;
if (a == 0 && c == 0) {
int s = i + j + 2;
if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][d]);
}
if (a == 1) {
int e = (b | c);
int s = i + j + 1 + !(c == 1);
if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + dp[it][j][c][d]);
}
}
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
dp[v][i][a][b] = dp2[i][a][b];
}
}
int main() {
scanf ("%d%d", &n, &m);
rep(i, 1, n) scanf ("%d", cost + i);
rep(i, 1, n - 1) {
scanf ("%d%d", &a, &b);
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 0);
int res = 0;
rep(i, 0, m)
rep(a, 0, 1)
rep(b, 0, 1)
maxi(res, dp[1][i][a][b]);
printf ("%d\n", res);
return 0;
}
Compilation message
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &n, &m);
~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:83:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
rep(i, 1, n) scanf ("%d", cost + i);
~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a, &b);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
1020 KB |
Output is correct |
| 2 |
Correct |
70 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
1148 KB |
Output is correct |
| 2 |
Correct |
1010 ms |
1656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1875 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
551 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
624 ms |
2448 KB |
Output is correct |
| 2 |
Execution timed out |
2082 ms |
1868 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2092 ms |
2680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
2072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
