Submission #477042

#	Time	Username	Problem	Language	Result	Execution time	Memory
477042		SirCovidThe19th	Olympiads (BOI19_olympiads)	C++17	100 / 100	88 ms	1216 KiB

olympiads

#include <bits/stdc++.h> 
using namespace std; 

#define BTS bitset<505>
#define FOR(i, x, y) for (int i = x; i < y; i++)

int n, k, c, A[505][10];

struct frag{
    BTS bad; vector<int> use; int w = 0, fix = 0;
    frag(BTS _bad, int _fix) : bad(_bad), fix(_fix){
        bool take[n] = {}; int sm[k] = {};
        FOR(j, 0, k){
            int B = -1;
            FOR(i, 0, n) if (!bad[i] and !take[i] and (!~B or A[i][j] > A[B][j])) B = i;
            FOR(j1, 0, k) sm[j1] = max(sm[j1], A[B][j1]);
            take[B] = 1; use.push_back(B);
        }
        w = accumulate(sm, sm + k, 0);
    } 
};
bool operator<(const frag& a, const frag& b){ return a.w < b.w; }

int main(){
    cin >> n >> k >> c;
    FOR(i, 0, n) FOR(j, 0, k) cin >> A[i][j];
    priority_queue<frag> pq; pq.push({BTS(), 0}); 

    for (int i = 1; i <= c; i++){
        frag cur = pq.top(); pq.pop();
        if (i == c){ cout<<cur.w<<endl; return 0; }
        if (n - (cur.bad.count() + 1) < k) continue;
        while (cur.fix < cur.use.size()){
            BTS newBad = cur.bad; newBad[cur.use[cur.fix]] = 1;
            frag tmp = frag(newBad, cur.fix);
            pq.push(tmp); 
            cur.fix++;
        }
    }
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:32:39: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if (n - (cur.bad.count() + 1) < k) continue;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
olympiads.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while (cur.fix < cur.use.size()){
      |                ~~~~~~~~^~~~~~~~~~~~~~~~

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