oj.uz

Submission #161172

# Submission time Handle Problem Language Result Execution time Memory
161172 2019-11-01T08:34:48 Z Minnakhmetov Chase (CEOI17_chase) C++14
40 / 100
 3296 ms 3064 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const ll INF = 1e18;
const int N = 1000 + 5, M = 105;
int a[N];
vector<int> g[N];
ll dp1[N][M], dp2[N][M][2], sum[N], dp3[M];
int n, m;

void upd(ll &a, ll b) {
    a = max(a, b);
}

ll ans = 0;

void dfs(int node, int anc) {
    for (int to : g[node]) {
        if (to != anc) {
            sum[node] += a[to];
            dfs(to, node);
        }
    }

    dp1[node][1] = sum[node];
    dp2[node][1][1] = sum[node];
    dp2[node][0][1] = -INF;

    ll up = (anc == -1 ? 0 : a[anc]);

    for (int k = 0; k < 2; k++) {
        memset(dp3, 0, sizeof(dp3));

        for (int to : g[node]) {
            if (to != anc) {
                for (int i = 0; i <= m; i++) {
                    ll cur = dp3[m - i] + dp1[to][i];
                    upd(ans, cur);
                }
                for (int i = 0; i <= m; i++) {
                    for (int j = 0; j < 2; j++) {
                        ll cur = dp2[to][i][j] + (j ? a[node] : 0);
                        upd(dp3[i], cur);
                        if (i < m) {
                            upd(dp3[i + 1], sum[node] - a[to] + up + cur);
                        }
                    }
                }

                for (int i = 1; i <= m; i++) {
                    upd(dp3[i], dp3[i - 1]);
                }
            }
        }
        reverse(all(g[node]));
    }

    for (int to : g[node]) {
        if (to != anc) {
            for (int i = 0; i <= m; i++) {
                upd(dp1[node][i], dp1[to][i]);
                if (i < m)
                    upd(dp1[node][i + 1] , dp1[to][i] + sum[node]);
                for (int j = 0; j < 2; j++) {
                    ll cur = dp2[to][i][j] + (j ? a[node] : 0);
                    upd(dp2[node][i][0], cur);
                    if (i < m)
                        upd(dp2[node][i + 1][1], cur + sum[node] - a[to]);
                }
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        upd(dp2[node][i][0], dp2[node][i - 1][0]);
        upd(dp2[node][i][1], dp2[node][i - 1][1]);
        upd(dp1[node][i], dp1[node][i - 1]);
    }

    for (int i = 0; i <= m; i++) {
        upd(ans, dp2[node][i][0]);
        upd(ans, dp2[node][i][1]);
        upd(ans, dp1[node][i]);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 0; i < n; i++) {
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        memset(sum, 0, sizeof(sum));
        dfs(i, -1);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 6 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2812 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 6 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2812 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 3158 ms 2936 KB Output is correct
8 Correct 396 ms 2936 KB Output is correct
9 Correct 432 ms 3064 KB Output is correct
10 Correct 3296 ms 2956 KB Output is correct
11 Correct 1128 ms 3036 KB Output is correct
12 Correct 541 ms 3036 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 6 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2812 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 3158 ms 2936 KB Output is correct
8 Correct 396 ms 2936 KB Output is correct
9 Correct 432 ms 3064 KB Output is correct
10 Correct 3296 ms 2956 KB Output is correct
11 Correct 1128 ms 3036 KB Output is correct
12 Correct 541 ms 3036 KB Output is correct
13 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -