Submission #618855

#	Time	Username	Problem	Language	Result	Execution time	Memory
618855		nghiass001	Chase (CEOI17_chase)	C++17	0 / 100	196 ms	182000 KiB

chase

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define REPD(i, r, l) for(int i = (r) - 1; i >= (l); --i)
using namespace std;
const int N = 1e5 + 5, M = 105;
int n, m, a[N];
long long res, sum[N], dp[N][M], dp2[N][M]; /// bottom-up / top-down
vector<int> S[N];

void Enter() {
    cin >> n >> m;
    FOR(i, 1, n) cin >> a[i];
    REP(i, 1, n) {
        int u, v;
        cin >> u >> v;
        S[u].push_back(v);
        S[v].push_back(u);
    }
}

void DFS(int u, int p) {
    sum[u] = a[u] + a[p];
    for(int v : S[u]) if (v != p) {
        DFS(v, u);
        sum[u] += a[v];
    }
    dp[u][1] = sum[u] - a[u];
    dp2[u][1] = sum[u];
    for(int v : S[u]) if (v != p) {
        REP(i, 1, m) {
            res = max(res, dp[u][i] + dp2[v][m - i] - a[u] - a[v]);
            res = max(res, dp2[u][i] + dp[v][m - i] - a[u] - a[v]);
        }
        REP(i, 0, m) {
            if (i) dp[u][i + 1] = max(dp[u][i + 1], dp[v][i] + sum[u] - a[u] - a[v]);
            dp2[u][i + 1] = max(dp2[u][i + 1], dp2[v][i] - a[u] - a[v]);
        }
    }
    res = max(res, dp[u][m]);
    res = max(res, dp2[u][m] - a[u]);
}

void Process() {
    DFS(1, 0);
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen("chase.inp", "r")) freopen("chase.inp", "r", stdin);
    Enter();
    Process();
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:53:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     if (fopen("chase.inp", "r")) freopen("chase.inp", "r", stdin);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30