Submission #162245

#	Time	Username	Problem	Language	Result	Execution time	Memory
162245		karma	Chase (CEOI17_chase)	C++14	100 / 100	697 ms	332124 KiB

chase

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

const int N = int(1e5) + 3;

int n, k, u, v, c[N], p[N];
ll s[N], res, f[N][101][2], g[N][101][2];
vector<int> a[N];

void DFS(int u) {
    f[u][1][1] = g[u][1][1] = s[u];
    for(int v: a[u]) {
        if(v == p[u]) continue;
        p[v] = u; DFS(v);
        for(int j = 1, t = k - 1; j <= k; ++j, --t) {
           res = max({res, f[v][j][0] + g[u][t][0], f[v][j][1] + g[u][t][0]});
           res = max(res, max(f[v][j][0], f[v][j][1]) + g[u][t][1] - c[v]);
           res = max({res, g[v][j][0] + f[u][t][0], g[v][j][0] + f[u][t][1]});
           res = max(res, g[v][j][1] - c[u] + max(f[u][t][0], f[u][t][1]));
        }
        for(int j = 1; j <= k; ++j) {
           f[u][j][0] = max({f[u][j][0], f[v][j][0], f[v][j][1]});
           f[u][j][1] = max(f[u][j][1], max(f[v][j - 1][0], f[v][j - 1][1]) + s[u] - c[v]);
           g[u][j][0] = max({g[u][j][0], g[v][j][0], g[v][j][1] - c[u]});
           g[u][j][1] = max(g[u][j][1], max(g[v][j - 1][0], g[v][j - 1][1] - c[u]) + s[u]);
           res = max({res, g[u][j][1], f[u][j][1]});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "chase"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    Cin(n, k);
    for(int i = 1; i <= n; ++i) Cin(c[i]);
    for(int i = 1; i < n; ++i) {
        Cin(u, v);
        a[u].pb(v), a[v].pb(u);
        s[u] += c[v], s[v] += c[u];
    }
    DFS(1);
    cout << res;
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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