oj.uz

Submission #945086

# Submission time Handle Problem Language Result Execution time Memory
945086 2024-03-13T11:41:18 Z vjudge1 Chase (CEOI17_chase) C++17
70 / 100
 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

chase.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory 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

Subtask #4
0 / 30.0

# Verdict Execution time Memory 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 -