oj.uz

답안 #477042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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