oj.uz

Submission #241513

# Submission time Handle Problem Language Result Execution time Memory
241513 2020-06-24T10:44:49 Z NONAME Dostavljač (COCI18_dostavljac) C++14
140 / 140
 332 ms 3468 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;

const ll MX = 2e9;
const ll N = 1e5 + 500;

int n, m;
ll a[510], f[510][510][2];
vector <int> g[510];

void upd(ll &a, ll b) { a = max(a, b); }

void dfs(int v, int pr) {
    f[v][1][0] = a[v];

    for (int u : g[v]) {
        if (u == pr)
            continue;

        dfs(u, v);

        for (int tv = m; tv >= 0; --tv)
        for (int tu = m; tu >= 0; --tu) {
            if (tv + tu + 2 <= m) {
                upd(f[v][tv + tu + 2][0], f[v][tv][0] + f[u][tu][0]);
                upd(f[v][tv + tu + 2][1], f[v][tv][1] + f[u][tu][0]);
            }

            if (tv + tu + 1 <= m)
                upd(f[v][tv + tu + 1][1], f[v][tv][0] + max(f[u][tu][0], f[u][tu][1]));
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    #ifdef _LOCAL
//        freopen("in", "r", stdin);
//        freopen("out", "w", stdout);
//    #endif // _LOCAL

    cin >> n >> m;
    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;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(0, 0);

    ll ans = 0;

    for (int i = 0; i <= m; ++i)
    for (int t = 0; t < 2; ++t)
        upd(ans, f[0][i][t]);

    cout << ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 896 KB Output is correct
2 Correct 8 ms 768 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 51 ms 1144 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1528 KB Output is correct
2 Correct 32 ms 1656 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2040 KB Output is correct
2 Correct 204 ms 1672 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 2808 KB Output is correct
2 Correct 74 ms 2936 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 3468 KB Output is correct
2 Correct 37 ms 2424 KB Output is correct