Submission #1027759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027759		d4xn	Chase (CEOI17_chase)	C++17	0 / 100	4027 ms	173648 KiB

chase

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 100000, NN = 99999, V = 101;

int n, v, a[N];
ll ans, sum[N], dp[2][V][NN];
pair<int, int> edge[NN];
vector<pair<int, int>> adj[N];

ll dfs(int d, int nwV, int e) {
  if (dp[d][nwV][e] != -1) return dp[d][nwV][e];
  
  dp[d][nwV][e] = 0;

  int x = edge[e].first;
  int y = edge[e].second;
  if (d) swap(x, y);

  // estoy en x y vengo de y

  // lanzo pan
  if (nwV) {
    for (auto& [z, idx] : adj[x]) {
      if (z == y) continue;

      int nwD = (edge[idx].first == z ? 0 : 1);
      ll SEXO = sum[x] - a[y];
      dp[d][nwV][e] = max(dp[d][nwV][e], SEXO + dfs(nwD, nwV-1, idx));
    }
  }

  // no lanzo pan
  for (auto& [z, idx] : adj[x]) {
    if (z == y) continue;

    int nwD = (edge[idx].first == z ? 0 : 1);
    dp[d][nwV][e] = max(dp[d][nwV][e], dfs(nwD, nwV, idx));
  }

  return dp[d][nwV][e];
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  cin >> n >> v;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n-1; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    
    adj[x].push_back(make_pair(y, i));
    adj[y].push_back(make_pair(x, i));
  
    edge[i] = make_pair(x, y);
  }

  memset(sum, 0, sizeof(sum));
  for (int i = 0; i < n; i++) {
    for (auto& [j, idx] : adj[i]) {
      sum[i] += a[j];
    }
  }

  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j <= v; j++) {
      dp[0][j][i] = dp[1][j][i] = -1;
    }
  }

  ans = 0;
  for (int i = 0; i < n-1; i++) {
    ans = max(ans, dfs(0, v, i));
    ans = max(ans, dfs(1, v, i)); 
  }

  for (int i = 0; i < n; i++) {
    for (auto& [j, idx] : adj[i]) {
      int d = (edge[idx].first == j ? 0 : 1);
      ans = max(ans, sum[i] + dfs(d, v-1, idx));
    }
  }

  cout << ans << "\n";
}

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