oj.uz

Submission #945084

# Submission time Handle Problem Language Result Execution time Memory
945084 2024-03-13T11:40:19 Z vjudge1 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 89168 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; 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;
}
// a

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 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4696 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 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 207 ms 4700 KB Output is correct
8 Correct 26 ms 4696 KB Output is correct
9 Correct 22 ms 4696 KB Output is correct
10 Correct 206 ms 4936 KB Output is correct
11 Correct 79 ms 4700 KB Output is correct
12 Correct 34 ms 4700 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4085 ms 89168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 207 ms 4700 KB Output is correct
8 Correct 26 ms 4696 KB Output is correct
9 Correct 22 ms 4696 KB Output is correct
10 Correct 206 ms 4936 KB Output is correct
11 Correct 79 ms 4700 KB Output is correct
12 Correct 34 ms 4700 KB Output is correct
13 Execution timed out 4085 ms 89168 KB Time limit exceeded
14 Halted 0 ms 0 KB -