Algoogle

Algorithm for Programming Contest

PKU 2436 Disease Management

Category: PKU Tag: implementation

Disease Management

問題概要


解法


含むことができる病気を全通り試す. ビットでやるとやりやすい.

コード


(2436.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <algorithm>
#include <cstdio>

using namespace std;

int N, D, K;
int cows[1024];

int main(){
    scanf("%d%d%d", &N, &D, &K);
    for(int i = 0; i < N; i++){
        int t; scanf("%d", &t);
        while(t--){
            int d; scanf("%d", &d);
            d--;
            cows[i] |= 1 << d;
        }
    }
    int ans = 0;
    for(int S = 0; S < (1 << D); S++){
        int cnt = 0;
        if(__builtin_popcount(S) <= K)
            for(int i = 0; i < N; i++)
                if((S | cows[i]) == S) cnt++;
        ans = max(ans, cnt);
    }
    printf("%d\n", ans);
    return 0;
}

Comments