제출 #1289168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289168		ninhtay	Dostavljač (COCI18_dostavljac)	C++20	140 / 140	12 ms	628 KiB

dostavljac

#include <bits/stdc++.h>
using namespace std;
const long long NEG = -1e15;
int N, M;
long long A[505];
vector<int> g[505];
bool vis[505];

pair<vector<long long>, vector<long long>> dfs(int u) {
    vis[u] = true;
    vector<long long> f_ret(M + 1, NEG), f_open(M + 1, NEG);
    f_ret[0] = f_open[0] = 0;
    if (M >= 1) f_ret[1] = f_open[1] = A[u];

    for (int v : g[u]) if (!vis[v]) {
        auto [cr, co] = dfs(v);
        vector<long long> new_ret = f_ret, new_open = f_open;
        for (int t1 = 0; t1 <= M; t1++) {
            if (f_ret[t1] <= NEG/2 && f_open[t1] <= NEG/2) continue;
            for (int t2 = 0; t2 <= M; t2++) {
                if (cr[t2] <= NEG/2) continue;
                int cost = t1 + t2 + 2;
                if (cost <= M) {
                    if (f_ret[t1] > NEG/2) new_ret[cost] = max(new_ret[cost], f_ret[t1] + cr[t2]);
                    if (f_open[t1] > NEG/2) new_open[cost] = max(new_open[cost], f_open[t1] + cr[t2]);
                }
            }
            for (int t2 = 0; t2 <= M; t2++) {
                if (co[t2] <= NEG/2) continue;
                int cost = t1 + t2 + 1;
                if (cost <= M && f_ret[t1] > NEG/2)
                    new_open[cost] = max(new_open[cost], f_ret[t1] + co[t2]);
            }
        }
        f_ret.swap(new_ret);
        f_open.swap(new_open);
    }
    return {f_ret, f_open};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto [fr, fo] = dfs(1);
    long long ans = 0;
    for (int t = 0; t <= M; t++) ans = max({ans, fr[t], fo[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