Submission #941722

#	Time	Username	Problem	Language	Result	Execution time	Memory
941722		vjudge1	Chase (CEOI17_chase)	C++17	0 / 100	514 ms	524288 KiB

chase

#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<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, -INF)));
  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];
    }
    
    dp[u][0][1] = 0;
    for (int v : adj[u]) {
      if (v == p) continue;
      
      dp[u][0][1] = max(dp[u][0][1], dp[v][0][0]);
      for (int i = 1; i <= k; ++i) {
        // colectez
        dp[u][i][1] = max(dp[u][i][1], S + dp[v][i - 1][1]);
        
        // nu colectez
        dp[u][i][1] = max(dp[u][i][1], dp[v][i][0]);
      }
    }
    for (int i = 0; i <= k; ++i) {
      dp[u][i][1] = max(dp[u][i][1], 0LL);
      dp[u][i][0] = dp[u][i][1] - a[u];
    }
  };
  
  dfs(1, 0);
  cout << dp[1][k][1] << endl;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30