## Submission #234096

# Submission time Handle Problem Language Result Execution time Memory
234096 2020-05-23T04:52:24 Z Fischer Dostavljač (COCI18_dostavljac) C++14
140 / 140
9 ms 2432 KB
```/**
* code generated by JHelper
* @author Miguel Mini
*/

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 505;
int A[maxn];
int n, m;
vi g[maxn];
int dp[maxn][maxn][2];
int sz[maxn];

int dfs(int x, int p) {
sz[x] = 1;
dp[x][0][0] = dp[x][0][1] = 0;
dp[x][1][0] = dp[x][1][1] = A[x];
trav(v, g[x]) {
if (v == p) continue;
dfs(v, x);
sz[x] += sz[v];
for (int i = min(m, 3 * sz[x] - 2); i >= 1; --i) {
for (int j = min(i, 3 * sz[v]); j >= max(1, i - 3 * (sz[x] - sz[v])); --j) {
dp[x][i][0] = max(dp[x][i][0], dp[x][i - j][1] + dp[v][j - 1][0]);
if (j >= 2) {
dp[x][i][0] = max(dp[x][i][0], dp[x][i - j][0] + dp[v][j - 2][1]);
dp[x][i][1] = max(dp[x][i][1], dp[x][i - j][1] + dp[v][j - 2][1]);
}
}
}
}
}

class COC_18_dostavljac {
public:
void solveOne(istream& in, ostream& out) {
in >> n >> m;
m = min(m, 3*n - 2);
re(i, 1, n + 1) {
in >> A[i];
}
memset(dp, 0, sizeof dp);
re(i, 1, n+1) g[i].clear();
re(i, 1, n) {
int a, b;
in >> a >> b;
g[a].eb(b);
g[b].eb(a);
}
dfs(1, 0);
int ans = 0;
for (int i = 0; i <= m; ++i) {
ans = max(ans, dp[1][i][0]);
}
out << ans << endl;
}

void solve(istream& in, ostream& out) {
int testNumber = 1;
//in >> testNumber;
re(tc, 1, testNumber+1) {
//out << "Case #" << tc << ": ";
solveOne(in, out);
}
}
};

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
COC_18_dostavljac solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}```

### Compilation message

```dostavljac.cpp: In function 'int dfs(int, int)':
dostavljac.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^```

#### Subtask #1 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct

#### Subtask #2 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct

#### Subtask #3 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct

#### Subtask #4 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct

#### Subtask #5 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct

#### Subtask #6 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2432 KB Output is correct

#### Subtask #7 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2432 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct

#### Subtask #8 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2304 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct

#### Subtask #9 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2304 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct

#### Subtask #10 14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2432 KB Output is correct
2 Correct 7 ms 2304 KB Output is correct