oj.uz

답안 #945082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945082 2024-03-13T11:39:08 Z vjudge1 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 91344 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;
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4708 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 4696 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4708 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 4696 KB Output is correct
7 Correct 210 ms 4816 KB Output is correct
8 Correct 25 ms 4696 KB Output is correct
9 Correct 21 ms 4776 KB Output is correct
10 Correct 238 ms 4700 KB Output is correct
11 Correct 78 ms 4776 KB Output is correct
12 Correct 34 ms 4700 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4019 ms 91344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4708 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 4696 KB Output is correct
7 Correct 210 ms 4816 KB Output is correct
8 Correct 25 ms 4696 KB Output is correct
9 Correct 21 ms 4776 KB Output is correct
10 Correct 238 ms 4700 KB Output is correct
11 Correct 78 ms 4776 KB Output is correct
12 Correct 34 ms 4700 KB Output is correct
13 Execution timed out 4019 ms 91344 KB Time limit exceeded
14 Halted 0 ms 0 KB -