oj.uz

Submission #241510

# Submission time Handle Problem Language Result Execution time Memory
241510 2020-06-24T10:40:31 Z NONAME Dostavljač (COCI18_dostavljac) C++14
0 / 140
 337 ms 3320 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 = 1; i <= m; ++i)
    for (int t = 0; t < 2; ++t)
        upd(ans, f[0][i][t]);

    cout << ans << "\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 640 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -