제출 #516706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516706		KoD	Džumbus (COCI19_dzumbus)	C++17	110 / 110	61 ms	3348 KiB

dzumbus

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

using i64 = std::int64_t;
constexpr i64 inf = std::numeric_limits<i64>::max() / 2;

void setmin(i64& x, const i64 y) {
    if (x > y) {
        x = y;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> S(N);
    for (auto& x : S) {
        std::cin >> x;
    }
    vector<vector<int>> graph(N);
    while (M--) {
        int a, b;
        std::cin >> a >> b;
        a -= 1, b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<char> done(N);
    vector<i64> all = {0};
    for (int root = 0; root < N; ++root) {
        if (done[root]) {
            continue;
        }
        const auto result = rec_lambda([&](auto&& dfs, const int u) -> vector<array<i64, 3>> {
            done[u] = true;
            vector<array<i64, 3>> dp(2);
            for (auto& a : dp) {
                a.fill(inf);
            }
            dp[0][0] = 0;
            dp[0][1] = S[u];
            for (const int v : graph[u]) {
                if (done[v]) {
                    continue;
                }
                const auto add = dfs(v);
                const int n = dp.size(), m = add.size();
                vector<array<i64, 3>> next(n + m - 1);
                for (auto& a : next) {
                    a.fill(inf);
                }
                for (int i = 0; i < n; ++i) {
                    for (int k = 0; k < 3; ++k) {
                        if (dp[i][k] == inf) {
                            continue;
                        }
                        for (int j = 0; j < m; ++j) {
                            for (int l = 0; l < 3; ++l) {
                                if (add[j][l] == inf) {
                                    continue;
                                }
                                const int nk = (k == 1 and l >= 1 ? 2 : k);
                                const int nl = (l == 1 and k >= 1 ? 2 : l);
                                setmin(next[i + j + (nk - k) + (nl - l)][nk], dp[i][k] + add[j][l]);
                            }
                        }
                    }
                }
                dp = std::move(next);
            }
            return dp;
        })(root);
        const int n = all.size(), m = result.size();
        vector<i64> next(n + m - 1, inf);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                setmin(next[i + j], all[i] + std::min({result[j][0], result[j][1], result[j][2]}));
            }
        }
        all = std::move(next);
    }
    for (int i = N; i > 0; --i) {
        setmin(all[i - 1], all[i]);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        i64 x;
        std::cin >> x;
        std::cout << std::upper_bound(all.begin(), all.end(), x) - all.begin() - 1 << '\n';
    }
    return 0;
}

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