제출 #835813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835813		elkernos	Chase (CEOI17_chase)	C++17	100 / 100	332 ms	265000 KiB

chase

// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on

template<typename T>
void ckmax(T& a, T b) { a = max(a, b); }

int32_t main()
{
    int n = in, v = in;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) c[i] = in;
    vector<vector<int>> g(n + 1);
    vector<i64> ile(n + 1);
    for(int i = 1; i < n; i++) {
        int a = in, b = in;
        g[a].emplace_back(b), g[b].emplace_back(a);
        ile[a] += c[b]; ile[b] += c[a];
    }
    i64 ans = 0;
    vector<vector<i64>> dpup(n + 1, vector<i64>(v + 1)), dpdown(n + 1, vector<i64>(v + 1));
    function<void(int, int)> dfs = [&](int u, int p) {
        dpup[u][1] = ile[u];
        vector<i64> przepisz_up(v + 1), przepisz_down(v + 1);
        for(int to : g[u]) {
            if(to == p) continue;
            dfs(to, u);
            for(int j = 1; j <= v; j++) {
                i64 dist_up = max(dpup[to][j], dpup[to][j - 1] + ile[u] - c[to]);
                i64 dist_down = max(dpdown[to][j], dpdown[to][j - 1] + ile[to] - c[u]);
                przepisz_up[j] = dist_up; przepisz_down[j] = dist_down;
                if(j != v) {
                    ckmax(ans, dpup[u][v - j] + dist_down);
                    ckmax(ans, dpdown[u][v - j] + dist_up);
                    ckmax(ans, dpdown[to][j] + ile[u]);
                }
            }
            for(int j = 1; j <= v; j++) {
                ckmax(dpup[u][j], przepisz_up[j]); ckmax(dpdown[u][j], przepisz_down[j]);
                ckmax(ans, dpup[u][j]);
            }
        }
    };
    if(v == 0) { cout << 0; exit(0); }
    dfs(1, 0); cout << ans << endl;
}

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