oj.uz

Submission #1014240

# Submission time Handle Problem Language Result Execution time Memory
1014240 2024-07-04T15:03:11 Z MilosMilutinovic Chase (CEOI17_chase) C++14
100 / 100
 3593 ms 348212 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++) {
              {
                long long ft = (he == 0 ? 0 : -a[v]);
                res = max(res, dp[v][i][0][me] + dp[u][j][1][he] + ft);
              }
              {
                long long 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++) {
            long long 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++) {
            long long 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 1 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 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 33 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 33 ms 4688 KB Output is correct
11 Correct 5 ms 4696 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3560 ms 345868 KB Output is correct
2 Correct 3593 ms 347912 KB Output is correct
3 Correct 3356 ms 338380 KB Output is correct
4 Correct 153 ms 338004 KB Output is correct
5 Correct 3506 ms 337880 KB Output is correct
6 Correct 3312 ms 338060 KB Output is correct
7 Correct 3477 ms 337868 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 33 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 33 ms 4688 KB Output is correct
11 Correct 5 ms 4696 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 3560 ms 345868 KB Output is correct
14 Correct 3593 ms 347912 KB Output is correct
15 Correct 3356 ms 338380 KB Output is correct
16 Correct 153 ms 338004 KB Output is correct
17 Correct 3506 ms 337880 KB Output is correct
18 Correct 3312 ms 338060 KB Output is correct
19 Correct 3477 ms 337868 KB Output is correct
20 Correct 3397 ms 337896 KB Output is correct
21 Correct 171 ms 338000 KB Output is correct
22 Correct 3245 ms 337872 KB Output is correct
23 Correct 149 ms 338004 KB Output is correct
24 Correct 3192 ms 337956 KB Output is correct
25 Correct 3262 ms 337880 KB Output is correct
26 Correct 3286 ms 348212 KB Output is correct
27 Correct 3137 ms 347988 KB Output is correct