oj.uz

답안 #583042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583042 2022-06-24T17:53:50 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 97604 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int B = 100 + 7;
const ll INF = (ll) 1e18 + 7;
int n, bread_have, pigs[N];
ll gain[N];
ll dp[N][B];
vector<int> g[N];

void dfs(int a, int p = 0) {
  for (int i = 0; i <= bread_have; i++) {
    dp[a][i] = 0;
  }
  gain[a] = 0;
  for (auto &b : g[a]) {
    if (b != p) {
      dfs(b, a);
      gain[a] += pigs[b];
      for (int i = 1; i <= bread_have; i++) {
        dp[a][i] = max(dp[a][i], dp[b][i]);
      }
    }
  }

  for (int i = bread_have - 1; i >= 0; i--) {
    dp[a][i + 1] = max(dp[a][i + 1], dp[a][i] + gain[a]);
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  ///freopen ("input.txt", "r", stdin);

  cin >> n >> bread_have;
  for (int i = 1; i <= n; i++) {
    cin >> pigs[i];
  }

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  ll sol = -INF;
  for (int root = 1; root <= n; root++) {
    dfs(root);
    for (int i = 1; i <= bread_have; i++) {
      assert(dp[root][i - 1] <= dp[root][i]);
    }
    sol = max(sol, dp[root][bread_have]);
  }
  cout << sol << "\n";
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 272 ms 3624 KB Output is correct
8 Correct 40 ms 3620 KB Output is correct
9 Correct 35 ms 3540 KB Output is correct
10 Correct 254 ms 3596 KB Output is correct
11 Correct 144 ms 3592 KB Output is correct
12 Correct 57 ms 3568 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 272 ms 3624 KB Output is correct
8 Correct 40 ms 3620 KB Output is correct
9 Correct 35 ms 3540 KB Output is correct
10 Correct 254 ms 3596 KB Output is correct
11 Correct 144 ms 3592 KB Output is correct
12 Correct 57 ms 3568 KB Output is correct
13 Execution timed out 4058 ms 97604 KB Time limit exceeded
14 Halted 0 ms 0 KB -