oj.uz

Submission #945337

# Submission time Handle Problem Language Result Execution time Memory
945337 2024-03-13T16:19:18 Z vjudge1 Chase (CEOI17_chase) C++17
100 / 100
 183 ms 165204 KB 
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 100228;
const int MAXV = 100 + 7;

int n, k, a[MAXN];
vector<int> g[MAXN];
ll dp1[MAXN][MAXV], dp2[MAXN][MAXV];
ll res = 0;

void dfs(int u, int p = 0) {
    ll s = 0;
    for (auto h: g[u]) {
        s += a[h];
    }
    vector<int> kids;
    dp2[u][1] = s;
    for (auto h: g[u]) {
        if (h == p) {
            continue;
        }
        kids.pb(h);
        dfs(h, u);
        for (int i = 1; i <= k; i++) {
            chkmax(res, dp2[u][i] + dp1[h][k - i]);
        }
        for (int i = 1; i <= k; i++) {
            chkmax(dp1[u][i], max(dp1[h][i], dp1[h][i - 1] + s - a[p]));
            chkmax(dp2[u][i], max(dp2[h][i], dp2[h][i - 1] + s - a[h]));
        }
    }
    for (int i = 1; i <= k; i++) {
        dp2[u][i] = 0;
    }
    dp2[u][1] = s;
    reverse(all(kids));
    for (auto h: kids) {
        for (int i = 1; i <= k; i++) {
            chkmax(res, dp2[u][i] + dp1[h][k - i]);
        }
        for (int i = 1; i <= k; i++) {
            chkmax(dp2[u][i], max(dp2[h][i], dp2[h][i - 1] + s - a[h]));
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    cout << res << '\n';
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 7256 KB Output is correct
8 Correct 2 ms 7348 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 7432 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 145744 KB Output is correct
2 Correct 134 ms 145948 KB Output is correct
3 Correct 106 ms 94572 KB Output is correct
4 Correct 90 ms 162896 KB Output is correct
5 Correct 161 ms 165204 KB Output is correct
6 Correct 170 ms 165032 KB Output is correct
7 Correct 183 ms 164944 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 7256 KB Output is correct
8 Correct 2 ms 7348 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 7432 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 152 ms 145744 KB Output is correct
14 Correct 134 ms 145948 KB Output is correct
15 Correct 106 ms 94572 KB Output is correct
16 Correct 90 ms 162896 KB Output is correct
17 Correct 161 ms 165204 KB Output is correct
18 Correct 170 ms 165032 KB Output is correct
19 Correct 183 ms 164944 KB Output is correct
20 Correct 161 ms 165176 KB Output is correct
21 Correct 51 ms 94332 KB Output is correct
22 Correct 163 ms 164688 KB Output is correct
23 Correct 92 ms 162876 KB Output is correct
24 Correct 167 ms 165204 KB Output is correct
25 Correct 108 ms 94552 KB Output is correct
26 Correct 141 ms 146004 KB Output is correct
27 Correct 143 ms 145876 KB Output is correct