oj.uz

Submission #396531

# Submission time Handle Problem Language Result Execution time Memory
396531 2021-04-30T07:02:28 Z KoD Olympiads (BOI19_olympiads) C++17
100 / 100
 11 ms 10728 KB 
#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T> bool setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

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

struct State {
    u32 score;
    Vec<u32> member;
    Vec<u32> type;
    bool operator<(const State& other) const { return score < other.score; }
};

void BOI19_Olympiads_main() {
    usize N, K, C;
    std::cin >> N >> K >> C;
    Vec<Vec<u32>> score(K, Vec<u32>(N));
    for (const auto j : rep(0, N)) {
        for (const auto i : rep(0, K)) {
            std::cin >> score[i][j];
        }
    }
    Vec<Vec<usize>> order(K, Vec<usize>(N));
    for (const auto i : rep(0, K)) {
        auto& vec = order[i];
        std::iota(vec.begin(), vec.end(), (usize)0);
        std::sort(vec.begin(), vec.end(), [&](const usize a, const usize b) {
            return score[i][a] > score[i][b];
        });
    }
    std::priority_queue<State> que;
    const auto evaluate = [&](State state) {
        while (state.member.size() < K) {
            const auto i = state.member.size();
            for (const auto x : order[i]) {
                if (state.type[x] == 0) {
                    state.member.push_back(x);
                    state.type[x] = 2;
                    break;
                }
            }
            if (state.member.size() == i) {
                return;
            }
        }
        state.score = 0;
        for (const auto i : rep(0, K)) {
            u32 max = 0;
            for (const auto x : state.member) {
                setmax(max, score[i][x]);
            }
            state.score += max;
        }
        que.push(std::move(state));
    };
    evaluate(State{0, {}, Vec<u32>(N, 0)});
    while (!que.empty()) {
        auto state = que.top();
        que.pop();
        C -= 1;
        if (C == 0) {
            std::cout << state.score << '\n';
            return;
        }
        Vec<usize> change;
        while (!state.member.empty() and state.type[state.member.back()] == 2) {
            change.push_back(state.member.back());
            state.type[state.member.back()] = 0;
            state.member.pop_back();
        }
        usize last = -1;
        while (!change.empty()) {
            const auto exclude = change.back();
            change.pop_back();
            state.type[exclude] = 1;
            if (~last) {
                state.member.push_back(last);
            }
            last = exclude;
            evaluate(state);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    BOI19_Olympiads_main();
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 696 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 3 ms 972 KB Output is correct
4 Correct 3 ms 720 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 8 ms 7024 KB Output is correct
4 Correct 8 ms 6732 KB Output is correct
5 Correct 7 ms 5580 KB Output is correct
6 Correct 3 ms 588 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 320 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 8 ms 7024 KB Output is correct
12 Correct 8 ms 6732 KB Output is correct
13 Correct 7 ms 5580 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 4 ms 1616 KB Output is correct
16 Correct 6 ms 5068 KB Output is correct
17 Correct 11 ms 10728 KB Output is correct
18 Correct 6 ms 4556 KB Output is correct
19 Correct 3 ms 332 KB Output is correct