oj.uz

Submission #677011

# Submission time Handle Problem Language Result Execution time Memory
677011 2023-01-02T05:08:39 Z dooompy Olympiads (BOI19_olympiads) C++17
100 / 100
 13 ms 1992 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int val[505][505];

vector<array<int, 3>> tot;

int n, k, c;

struct state {
    int best[7];

    bitset<505> banned;
    int idx;
    vector<int> team;
    ll score = 0;

    state(bitset<505> _banned, int _idx) : banned(_banned), idx(_idx) {
        vector<int>().swap(team);
        score = 0;

        fill(best, best+7, 0);

        int cnt = 0;

        for (int i = tot.size() - 1; i >= 0 && cnt < k; i--) {
            if (banned[tot[i][1]]) continue;
            if (best[tot[i][2]] > 0) continue;

            score += tot[i][0];
            best[tot[i][2]] = tot[i][0];

            cnt++;

            bool inteam = false;
            for (auto x : team) {
                if (x == tot[i][1]) {
                    inteam =true;
                    break;
                }
            }

            if (!inteam) {
                team.push_back(tot[i][1]);
            }
        }

        if (team.size() < k) {
            for (int i = tot.size()  - 1; i >= 0 && team.size() < k; i--) {
                if (banned[tot[i][1]]) continue;

                bool onteam = false;
                for (auto x : team) {
                    if (x == tot[i][1]) {
                        onteam =true;
                        break;
                    }
                }

                if (onteam) continue;

                team.push_back(tot[i][1]);
            }
        }
    }

    bool operator<(state o) const {
        return score < o.score;
    }
};

priority_queue<state> pq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    cin >> n >> k >> c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> val[i][j];
            tot.push_back({val[i][j], i, j});
        }
    }

    sort(tot.begin(), tot.end());

    pq.push({bitset<505>(), 0});

    for (int i = 1; i <= c; i++) {
        if (pq.empty()) {
            cout << -1 << endl;
            return 0;
        }

        auto cur = pq.top(); pq.pop();

        if (i == c) {
            cout << cur.score << endl;
            return 0;
        }

        while (cur.idx < k) {
            // ban current one

            bitset<505> nbanned = cur.banned;
            nbanned[cur.team[cur.idx]] = true;

            auto nw = state(nbanned, cur.idx);
            if (nw.team.size() == k) pq.push(nw);

            cur.idx++;
        }
    }
}

Compilation message

olympiads.cpp: In constructor 'state::state(std::bitset<505>, int)':
olympiads.cpp:76:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |         if (team.size() < k) {
      |             ~~~~~~~~~~~~^~~
olympiads.cpp:77:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |             for (int i = tot.size()  - 1; i >= 0 && team.size() < k; i--) {
      |                                                     ~~~~~~~~~~~~^~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:139:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |             if (nw.team.size() == k) pq.push(nw);
      |                 ~~~~~~~~~~~~~~~^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 3 ms 1352 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 8 ms 1412 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 10 ms 1364 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 3 ms 1352 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 1364 KB Output is correct
10 Correct 8 ms 1412 KB Output is correct
11 Correct 4 ms 1492 KB Output is correct
12 Correct 5 ms 1364 KB Output is correct
13 Correct 10 ms 1364 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 9 ms 1616 KB Output is correct
16 Correct 9 ms 1992 KB Output is correct
17 Correct 13 ms 1424 KB Output is correct
18 Correct 3 ms 1364 KB Output is correct
19 Correct 6 ms 1364 KB Output is correct