oj.uz

Submission #239786

# Submission time Handle Problem Language Result Execution time Memory
239786 2020-06-17T09:53:29 Z ne4eHbKa Dostavljač (COCI18_dostavljac) C++17
126 / 140
 245 ms 2432 KB 
#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.0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 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 12 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 47 ms 896 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1144 KB Output is correct
2 Correct 34 ms 1164 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1536 KB Output is correct
2 Correct 149 ms 1784 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1956 KB Output is correct
2 Correct 57 ms 1912 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2400 KB Output is correct
2 Correct 29 ms 2432 KB Output is correct