제출 #1027748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027748		d4xn	Chase (CEOI17_chase)	C++17	40 / 100	4066 ms	334072 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 int long long

const int N = 100000, V = 101;

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

int dfs(int f, int d, int nwV, int e) {
  if (dp[f][d][nwV][e] != -1) return dp[f][d][nwV][e];
  
  dp[f][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 (f && z == y) continue;

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

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

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

  return dp[f][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][0][j][i] = dp[0][1][j][i] = dp[1][0][j][i] = dp[1][1][j][i] = -1;
    }
  }

  /*if (n > 1000) {
    for (int i = 0; i < n-1; i++) {
      if (edge[i].first == 0) dfs(0, 0, v, i);
      if (edge[i].second == 0) dfs(0, 1, v, i); 
    }
  }
  else {*/
    for (int i = 0; i < n-1; i++) {
      dfs(0, 0, v, i);
      dfs(0, 1, v, i); 
    }
  //}

  ans = 0;
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j <= v; j++) {
      ans = max({ans, dp[0][0][j][i], dp[0][1][j][i]});
    }
  }
  cout << ans << "\n";
}

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