oj.uz

Submission #1014239

# Submission time Handle Problem Language Result Execution time Memory
1014239 2024-07-04T15:02:11 Z MilosMilutinovic Chase (CEOI17_chase) C++14
0 / 100
 3564 ms 345936 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100100;
const int K = 105;

long long dp[N][K][2][2];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<long long> s(n);
  for (int i = 0; i < n; i++) {
    for (int j : g[i]) {
      s[i] += a[j];
    }
  }
  long long res = 0;
  function<void(int, int)> Solve = [&](int v, int pv) {
    dp[v][1][0][1] = s[v];
    dp[v][1][1][1] = s[v];
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Solve(u, v);
      for (int i = 0; i <= k; i++) {
        for (int j = 0; i + j <= k; j++) {
          for (int me = 0; me < 2; me++) {
            for (int he = 0; he < 2; he++) {
              {
                int ft = (he == 0 ? 0 : -a[v]);
                res = max(res, dp[v][i][0][me] + dp[u][j][1][he] + ft);
              }
              {
                int ft = (me == 0 ? 0 : -a[u]);
                res = max(res, dp[v][i][1][me] + dp[u][j][0][he] + ft);
              }
            }
          }
        }
      }
      for (int i = 0; i <= k; i++) {
        for (int me = 0; me < 2; me++) {
          for (int he = 0; he < 2; he++) {
            int ft = (me == 0 ? 0 : s[v] - a[u]);
            dp[v][i + me][0][me] = max(dp[v][i + me][0][me], dp[u][i][0][he] + ft);
          }
        }
      }
      for (int i = 0; i <= k; i++) {
        for (int me = 0; me < 2; me++) {
          for (int he = 0; he < 2; he++) {
            int ft = (me == 0 ? 0 : s[v]);
            if (he == 1) {
              ft -= a[v];
            }
            dp[v][i + me][1][me] = max(dp[v][i + me][1][me], dp[u][i][1][he] + ft);
          }
        }
      }
    }
  };
  Solve(0, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      for (int d = 0; d < 2; d++) {
        for (int t = 0; t < 2; t++) {
          res = max(res, dp[i][j][d][t]);
        }
      }
    }
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3564 ms 345936 KB Output isn't correct
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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -