RiseOJ – 팀 구성

설명

농부 존은 매년 자신의 소 $$N$$ 마리를 주 박람회의 "최우수 소" 경연에 데려간다. 그의 숙적인 농부 폴도 자신의 소 $$M$$ 마리를 데리고 경연에 참가한다( $1 \leq N \leq 1000, 1 \leq M \leq 1000$ ).

행사에 참가한 $$N + M$$ 마리의 소는 각자 정수 점수를 하나씩 받는다. 그런데 올해의 최종 경연은 다음과 같이 $$K$$ 마리( $1 \leq K \leq 10$ )로 이루어진 팀 단위로 치러진다. 농부 존과 농부 폴은 각자 자신의 소 중 $$K$$ 마리로 팀을 구성한다. 두 팀의 소들은 서로 짝지어지는데, 존 팀에서 점수가 가장 높은 소는 폴 팀에서 점수가 가장 높은 소와, 존 팀에서 두 번째로 점수가 높은 소는 폴 팀에서 두 번째로 점수가 높은 소와 짝지어지는 식이다. 이 모든 짝에서 존의 소가 더 높은 점수를 가지면 존이 이긴다.

존이 경연에서 이기도록 존과 폴이 팀을 고를 수 있는 서로 다른 방법의 수를 세어 존을 도와주자. 즉, 존이 이기는 서로 다른 쌍(존의 $$K$$ 마리 소 집합, 폴의 $$K$$ 마리 소 집합)을 각각 세어야 한다. 답을 1,000,000,009로 나눈 나머지를 출력한다.

문제 출제: 브라이언 딘(Brian Dean), 윌리엄 루오(William Luo)

제약

문제 출제: 브라이언 딘(Brian Dean), 윌리엄 루오(William Luo)

입력 형식

입력의 첫째 줄에 $$N$$ , $$M$$ , $$K$$ 가 주어진다. $$K$$ 의 값은 $$N$$ 과 $$M$$ 을 넘지 않는다.

다음 줄에는 존의 소 $$N$$ 마리의 점수가 주어진다.

마지막 줄에는 폴의 소 $$M$$ 마리의 점수가 주어진다.

출력 형식

존이 이기도록 존과 폴이 팀을 고를 수 있는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 team.in · 출력을 쓸 파일 team.out

예제 1

입력

10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Platinum

올림피아드 > USACO > 2016-2017 > December > Platinum

태그

JudgeUSACO

팀 구성

평가 및 의견

풀이 제출