Submission #241513

#	Time	Username	Problem	Language	Result	Execution time	Memory
241513		NONAME	Dostavljač (COCI18_dostavljac)	C++14	140 / 140	332 ms	3468 KiB

dostavljac

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14