oj.uz

Submission #941727

# Submission time Handle Problem Language Result Execution time Memory
941727 2024-03-09T11:02:28 Z vjudge1 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 97832 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = pair<int, int>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

/*
dp[i][j][0/1] - subarborele lui i daca mai am j de aruncat si l-am colectat sau nu pe i
*/

const int INF = 1e16;

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, k;
  cin >> n >> k;
  
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  
  vector<vector<int>> dp(n + 1, vector<int>(k + 1));
  function<void(int, int)> dfs = [&](int u, int p) {
    int S = 0;
    for (int v : adj[u]) {
      if (v == p) continue;
      
      dfs(v, u);
      S += a[v];
    }
    
    for (int v : adj[u]) {
      if (v == p) continue;
      
      for (int i = 0; i <= k; ++i) {
        // colectez
        if (i > 0) dp[u][i] = max(dp[u][i], S + max(dp[v][i - 1], 0LL));
        
        // nu colectez
        dp[u][i] = max(dp[u][i], dp[v][i]);
      }
    }
  };
  
  int ans = 0;
  for (int r = 1; r <= n; ++r) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) dp[i][j] = -INF;
    }
    dfs(r, 0);
    ans = max(ans, dp[r][k]);
  }
  
  cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 230 ms 1400 KB Output is correct
8 Correct 29 ms 848 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 224 ms 1376 KB Output is correct
11 Correct 91 ms 856 KB Output is correct
12 Correct 41 ms 604 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 230 ms 1400 KB Output is correct
8 Correct 29 ms 848 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 224 ms 1376 KB Output is correct
11 Correct 91 ms 856 KB Output is correct
12 Correct 41 ms 604 KB Output is correct
13 Execution timed out 4094 ms 97832 KB Time limit exceeded
14 Halted 0 ms 0 KB -