Submission #396481

#	Time	Username	Problem	Language	Result	Execution time	Memory
396481		KoD	Olympiads (BOI19_olympiads)	C++17	100 / 100	19 ms	3444 KiB

olympiads

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

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

struct State {
    int sum, alive;
    Vec<int> idx;
    Vec<bool> use;
    bool operator < (const State& other) const {
        return sum < other.sum;
    }
};

int main() {
    int N, K;
    long long C;
    std::cin >> N >> K >> C;
    Vec<Vec<int>> get(N, Vec<int>(K));
    for (auto& v: get) {
        for (auto& x: v) {
            std::cin >> x;
        }
    }
    Vec<Vec<int>> order(K, Vec<int>(N));
    for (int i = 0; i < K; ++i) {
        auto& vec = order[i];
        std::iota(vec.begin(), vec.end(), 0);
        std::stable_sort(vec.begin(), vec.end(), [&](const int x, const int y) {
            return get[x][i] > get[y][i];
        });
    }
    Vec<Vec<long long>> binom(N + 1, Vec<long long>(K + 1));
    binom[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        binom[i][0] = 1;
        for (int j = 1; j <= K; ++j) {
            binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        }
    }
    const auto calc = [&](State& state) {
        state.sum = 0;
        for (int i = 0; i < K; ++i) {
            state.sum += get[order[i][state.idx[i]]][i];
        }
    };
    std::priority_queue<State> que;
    std::set<Vec<int>> seen;
    const auto push = [&](State&& state) {
        if (seen.find(state.idx) == seen.end()) {
            seen.insert(state.idx);
            calc(state);
            que.push(std::move(state));
        }
    };
    State initial {
        0, N,
        Vec<int>(K, 0),
        Vec<bool>(N, true),
    };
    push(std::move(initial));
    while (!que.empty()) {
        const auto state = que.top();
        que.pop();
        bool ok = true;
        std::set<int> set;
        for (int i = 0; i < K; ++i) {
            if (!state.use[order[i][state.idx[i]]]) {
                ok = false;
                break;
            }
            set.insert(order[i][state.idx[i]]);
        }
        if (ok) {
            C -= binom[state.alive - (int) set.size()][K - (int) set.size()];
            if (C <= 0) {
                std::cout << state.sum << '\n';
                return 0;
            }
        }
        for (int i = 0; i < K; ++i) {
            State next = state;
            auto& idx = next.idx[i];
            if (next.use[order[i][idx]]) {
                next.use[order[i][idx]] = false;
                next.alive -= 1;
            }
            while (idx < N and !next.use[order[i][idx]]) {
                idx += 1;
            }
            if (idx < N) {
                push(std::move(next));
            }
        }
    }
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32