풀이
학생들이 아는 모든 알고리즘의 수는 bit OR 연산과 같다.
이는 항상 같거나 증가한다.
모든 학생들이 아는 알고리즘의 수는 bit AND 연산과 같다.
이는 항상 같거나 감소한다.
따라서 누구는 빼고 누구는 넣고 할 것 없이 능력치 조건을 만족하는 범위 내의 모든 학생들을 선택해도 된다.
학생들을 능력치를 기준으로 정렬한 다음, 투 포인터를 사용하면 쉽게 답을 찾을 수 있다.
코드
#include <stdio.h>
#include <algorithm>
using namespace std;
const int n_ = 1e5 + 3;
int n, k, d, ans, l, r, cnt[33];
struct ABC { int alg, abt; } stu[n_];
int main() {
scanf("%d %d %d", &n, &k, &d);
for (int i = 0; i < n; i++) {
int m;
scanf("%d %d", &m, &stu[i].abt);
while (m--) {
int a;
scanf("%d", &a); --a;
stu[i].alg |= (1 << a);
}
}
sort(stu, stu + n, [](const ABC &i, const ABC &j) { return i.abt < j.abt; });
while (r < n) {
int now = 0;
while (stu[r].abt - stu[l].abt > d) {
for (int i = 0; i < k; i++) if (stu[l].alg & (1 << i)) cnt[i]--;
l++;
}
for (int i = 0; i < k; i++) if (stu[r].alg & (1 << i)) cnt[i]++;
for (int i = 0; i < k; i++) if (cnt[i] > 0 && cnt[i] < r - l + 1) now++;
ans = max(ans, now * (r - l + 1));
r++;
}
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이