래환이의 간식 이야기

시간 제한1초메모리 제한1024 MB

요약
학생들이 좋아하는 간식이 남아 있으면 하나씩 가져갈 때, 순서와 선택을 어떻게 정하든 간식을 받지 못하는 학생 수의 최댓값을 구한다.
난이도

보통10점 중 7점

유형
그리디, 수학, 조합론, 구현
정답자
아직 제출이 없습니다

문제

11번부터 NN번까지 학번이 매겨져 있는 NN명의 KSA 학생들은 오늘도 간식 시간만을 기다린다. 간식은 A, B, C 세 종류가 있는데, 각 학생별로 좋아하는 간식과 좋아하지 않는 간식의 종류가 정해져 있다. 간식 A, B, C는 각각 aa개, bb개, cc개 준비되어 있으며, a+b+c=Na+b+c=N이다.

NN명의 학생들은 우선 무작위 순서로 줄을 선 후, 차례대로 본인이 좋아하는 간식이 남아 있다면 그 중 무작위로 아무거나 하나를 가져간다. 하지만 본인이 좋아하지 않는 간식만 남아 있다면 간식을 가져가지 못한다. 각 학생이 어떤 종류의 간식을 좋아하는지가 주어질 때, 최악의 경우 간식을 가져가지 못하는 학생 수의 최댓값을 구해보자. 단, 학생들이 간식을 가져가는 순서는 무작위로 학번과는 무관하다는 점에 유의하라.

입력

첫 번째 줄에 정수 NN이 주어진다. (1≤N≤105)(1\le N\le 10^5)

두 번째 줄에 간식 A, B, C의 개수를 나타내는 세 정수 aa, bb, cc가 공백으로 구분되어 주어진다. (0≤a,b,c≤N;a+b+c=N)(0\le a,b,c\le N;a+b+c=N)

다음 NN개의 줄에 걸쳐 ii번째 줄에 세 정수 s_A,i,s_B,i,s_C,is\_{\text{A},i}, s\_{\text{B},i}, s\_{\text{C},i}가 공백으로 구분되어 주어진다. 이 값들은 ii번 학생이 각각 간식 A, 간식 B, 간식 C를 좋아한다면 11, 좋아하지 않는다면 00이다.

출력

간식을 가져가지 못하는 학생 수의 최댓값을 출력한다.

예제2

  1. 예제 1

    입력
    4
    1 1 2
    1 0 0
    0 0 0
    1 0 1
    0 1 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5
    2 2 1
    1 1 0
    0 0 1
    1 0 1
    0 1 1
    1 0 0
    
    예상 출력
    2