| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 945086 | 2024-03-13T11:41:18 Z | vjudge1 | Chase (CEOI17_chase) | C++17 | 213 ms | 89308 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby
typedef long long ll;
const int NMAX = 1e5;
const int VMAX = 100;
ll dp[NMAX + 1][VMAX + 1];
int a[NMAX + 1];
int V;
std::vector<int> g[NMAX + 1];
void dfs(int u, int p = 0) {
ll s = 0;
for (const auto &v : g[u]) {
if (v != p) {
dfs(v, u);
s += a[v];
}
}
for (const auto &v : g[u]) {
if (v != p) {
for (int i = 0; i <= V; i++) {
if (i != 0) {
dp[u][i] = std::max(dp[u][i], s + std::max(0LL, dp[v][i - 1]));
}
dp[u][i] = std::max(dp[u][i], dp[v][i]);
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n >> V;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ll answer = 0;
for (int i = 1; i <= (n <= 1000? n : 1); i++) {
for (int u = 1; u <= n; u++) {
for (int v = 0; v <= V; v++) {
dp[u][v] = -1e18;
}
}
dfs(i);
answer = std::max(answer, dp[i][V]);
}
std::cout << answer;
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4696 KB | Output is correct |
| 2 | Correct | 1 ms | 4700 KB | Output is correct |
| 3 | Correct | 1 ms | 4700 KB | Output is correct |
| 4 | Correct | 1 ms | 4700 KB | Output is correct |
| 5 | Correct | 1 ms | 4700 KB | Output is correct |
| 6 | Correct | 1 ms | 4700 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4696 KB | Output is correct |
| 2 | Correct | 1 ms | 4700 KB | Output is correct |
| 3 | Correct | 1 ms | 4700 KB | Output is correct |
| 4 | Correct | 1 ms | 4700 KB | Output is correct |
| 5 | Correct | 1 ms | 4700 KB | Output is correct |
| 6 | Correct | 1 ms | 4700 KB | Output is correct |
| 7 | Correct | 210 ms | 4700 KB | Output is correct |
| 8 | Correct | 26 ms | 4696 KB | Output is correct |
| 9 | Correct | 21 ms | 4700 KB | Output is correct |
| 10 | Correct | 213 ms | 4760 KB | Output is correct |
| 11 | Correct | 74 ms | 4696 KB | Output is correct |
| 12 | Correct | 34 ms | 4700 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 82 ms | 89308 KB | Output is correct |
| 2 | Correct | 79 ms | 89292 KB | Output is correct |
| 3 | Correct | 50 ms | 85708 KB | Output is correct |
| 4 | Correct | 46 ms | 85332 KB | Output is correct |
| 5 | Correct | 86 ms | 85332 KB | Output is correct |
| 6 | Correct | 87 ms | 85276 KB | Output is correct |
| 7 | Correct | 86 ms | 85444 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4696 KB | Output is correct |
| 2 | Correct | 1 ms | 4700 KB | Output is correct |
| 3 | Correct | 1 ms | 4700 KB | Output is correct |
| 4 | Correct | 1 ms | 4700 KB | Output is correct |
| 5 | Correct | 1 ms | 4700 KB | Output is correct |
| 6 | Correct | 1 ms | 4700 KB | Output is correct |
| 7 | Correct | 210 ms | 4700 KB | Output is correct |
| 8 | Correct | 26 ms | 4696 KB | Output is correct |
| 9 | Correct | 21 ms | 4700 KB | Output is correct |
| 10 | Correct | 213 ms | 4760 KB | Output is correct |
| 11 | Correct | 74 ms | 4696 KB | Output is correct |
| 12 | Correct | 34 ms | 4700 KB | Output is correct |
| 13 | Correct | 82 ms | 89308 KB | Output is correct |
| 14 | Correct | 79 ms | 89292 KB | Output is correct |
| 15 | Correct | 50 ms | 85708 KB | Output is correct |
| 16 | Correct | 46 ms | 85332 KB | Output is correct |
| 17 | Correct | 86 ms | 85332 KB | Output is correct |
| 18 | Correct | 87 ms | 85276 KB | Output is correct |
| 19 | Correct | 86 ms | 85444 KB | Output is correct |
| 20 | Incorrect | 88 ms | 87572 KB | Output isn't correct |
| 21 | Halted | 0 ms | 0 KB | - |