Submission #1256649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256649		MisterReaper	Džumbus (COCI19_dzumbus)	C++17	110 / 110	48 ms	44356 KiB

dzumbus

// File S.cpp created on 11.08.2025 at 20:22:27
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1000) + 5;
constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

struct Info {
    int siz;
    i64 x[3][max_N];
    Info() { std::fill_n(&x[0][0], max_N * 3, inf); }
    Info(i64 c) {
        std::fill_n(&x[0][0], max_N * 3, inf);
        siz = 1;
        x[0][0] = 0;
        x[1][0] = c;
    }
};

#define sz(x) int(x.size())

Info operator+ (const Info lhs, const Info rhs) {
    Info res;
    res.siz = lhs.siz + rhs.siz;
    for (int i = 0; i <= lhs.siz; ++i) {
        for (int j = 0; j <= rhs.siz; ++j) {
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[0][j]);
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[1][j]);
            chmin(res.x[0][i + j], lhs.x[0][i] + rhs.x[2][j]);
        }
    }
    for (int i = 0; i <= lhs.siz; ++i) {
        for (int j = 0; j <= rhs.siz; ++j) {
            chmin(res.x[1][i + j], lhs.x[1][i] + rhs.x[0][j]);
            chmin(res.x[2][i + j + 2], lhs.x[1][i] + rhs.x[1][j]);
            chmin(res.x[2][i + j + 1], lhs.x[1][i] + rhs.x[2][j]);
        }
    }
    for (int i = 0; i <= lhs.siz; ++i) {
        for (int j = 0; j <= rhs.siz; ++j) {
            chmin(res.x[2][i + j], lhs.x[2][i] + rhs.x[0][j]);
            chmin(res.x[2][i + j + 1], lhs.x[2][i] + rhs.x[1][j]);
            chmin(res.x[2][i + j], lhs.x[2][i] + rhs.x[2][j]);
        }
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        int U, V;
        std::cin >> U >> V;
        --U, --V;
        adj[U].emplace_back(V);
        adj[V].emplace_back(U);
    }

    std::vector<Info> f(N);
    std::vector<int> vis(N);
    auto dfs = [&](auto&& self, int v) -> void {
        f[v] = A[v];
        vis[v] = true;
        for (auto u : adj[v]) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
            self(self, u);
            f[v] = f[v] + f[u];
            // debug(v, f[v].x[0], f[v].x[1]);
        }
    };

    std::vector<i64> all = {0};
    for (int v = 0; v < N; ++v) {
        if (vis[v]) {
            continue;
        }
        dfs(dfs, v);
        std::vector<i64> nall;
        nall.assign(all.size() + f[v].siz + 1, inf);
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j <= f[v].siz; ++j) {
                chmin(nall[i + j], all[i] + f[v].x[0][j]);
            }
        }
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j <= f[v].siz; ++j) {
                chmin(nall[i + j], all[i] + f[v].x[1][j]);
            }
        }
        for (int i = 0; i < all.size(); ++i) {
            for (int j = 0; j <= f[v].siz; ++j) {
                chmin(nall[i + j], all[i] + f[v].x[2][j]);
            }
        }
        all = std::move(nall);
    }

    for (int i = int(all.size()) - 2; i >= 0; --i) {
        chmin(all[i], all[i + 1]);
    }

    debug(all);

    int Q;
    std::cin >> Q;

    while (Q--) {
        int S;
        std::cin >> S;

        int res = std::upper_bound(all.begin(), all.end(), S) - all.begin();
        std::cout << res - 1 << '\n';
    }

    return 0;
}

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