oj.uz

Submission #477042

# Submission time Handle Problem Language Result Execution time Memory
477042 2021-09-29T23:18:15 Z SirCovidThe19th Olympiads (BOI19_olympiads) C++17
100 / 100
 88 ms 1216 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 11 ms 204 KB Output is correct
3 Correct 10 ms 316 KB Output is correct
4 Correct 8 ms 204 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 588 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 7 ms 780 KB Output is correct
4 Correct 6 ms 588 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 332 KB Output is correct
2 Correct 23 ms 332 KB Output is correct
3 Correct 74 ms 828 KB Output is correct
4 Correct 69 ms 840 KB Output is correct
5 Correct 41 ms 416 KB Output is correct
6 Correct 6 ms 588 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 11 ms 204 KB Output is correct
3 Correct 10 ms 316 KB Output is correct
4 Correct 8 ms 204 KB Output is correct
5 Correct 7 ms 588 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 7 ms 780 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 31 ms 332 KB Output is correct
10 Correct 23 ms 332 KB Output is correct
11 Correct 74 ms 828 KB Output is correct
12 Correct 69 ms 840 KB Output is correct
13 Correct 41 ms 416 KB Output is correct
14 Correct 6 ms 588 KB Output is correct
15 Correct 43 ms 412 KB Output is correct
16 Correct 58 ms 864 KB Output is correct
17 Correct 88 ms 1216 KB Output is correct
18 Correct 62 ms 600 KB Output is correct
19 Correct 24 ms 340 KB Output is correct