제출 #239786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239786		ne4eHbKa	Dostavljač (COCI18_dostavljac)	C++17	126 / 140	245 ms	2432 KiB

dostavljac

#include <bits/stdc++.h>
using namespace std;

template<typename t> void umax(t &a, t b) {a = max(a, b);}
template<typename t> void umin(t &a, t b) {a = min(a, b);}

const int N = 505;

int n, m;
int a[N];
vector<int> g[N];
int f[N][N], h[N][N];
int p[N];

void rec(int v = 0, int pr = -1) {
    if(v) g[v].erase(find(g[v].begin(), g[v].end(), pr));

    for(int u : g[v]) {
        rec(u, v);
        for(int i = m; i >= 0; --i)
            for(int j = 0; j + 2 + i <= m; ++j)
                umax(f[v][i + 2 + j], f[v][i] + f[u][j]);
    }
    for(int i = m - 1; i; --i) umax(f[v][i], f[v][i - 1] + a[v]);
    for(int i = 1; i <= m; ++i) umax(f[v][i], f[v][i - 1]);

    for(int i = 0; i <= m; ++i) p[i] = 0;
    for(int u : g[v]) {
        for(int i = m; i >= 0; --i)
            for(int j = 0; j + 2 + i <= m; ++j) {
                umax(p[i + j + 2], p[i] + f[u][j]);
                umax(h[v][i + j + 1], p[i] + h[u][j]);
                umax(h[v][i + j + 2], h[v][i] + f[u][j]);
            }
    }
    for(int i = m; i; --i) umax(h[v][i], h[v][i - 1] + a[v]);
    for(int i = 1; i <= m; ++i) umax(h[v][i], h[v][i - 1]);
}

void solve() {
#ifdef _LOCAL
    memset(f, 0, sizeof f);
    memset(h, 0, sizeof h);
#endif // _LOCAL
    cin >> n >> m;
    for(int i = 0; i < n; ++i) cin >> a[i], g[i].clear();
    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);
    }
    rec();
    cout << h[0][m] << endl;
}

signed main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cerr << "case #" << i << endl;
        solve();
        cerr << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
#endif
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 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