14464번 - 소가 길을 건너간 이유 4 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 2843 | 803 | 596 | 28.654% |
문제
농부 존의 소들은 효율적으로 길을 건너는 방법을 터득하고 있다. 그들은 길 건너기의 달인인 닭의 도움을 받기로 했다.
안타깝게도 닭은 매우 바쁜 동물이라, 소를 도와줄 시간이 별로 없다. 농장에 C마리(1 ≤ C ≤ 20,000)의 닭이 있고, 1번부터 C번까지 번호가 붙어 있다. i번 닭은 정확히 Ti초에만 소를 도와줄 수 있다. 하지만 닭은 길 건너기의 달인이므로 소를 데리고도 순식간에 길을 건널 수 있다. 소는 할 일이 없어서 여유롭게 길을 건널 수 있다. 소는 총 N마리(1 ≤ N ≤ 20,000)가 있고, 마찬가지로 1번부터 N번까지 번호가 붙어 있다. j번 소는 Aj초부터 Bj초까지 길을 건널 수 있다. j번 소가 i번 닭의 도움을 받아 길을 건너려면 Aj ≤ Ti ≤ Bj를 만족해야 한다.
소는 최대 한 마리의 닭에게만 도움을 받을 수 있고, 닭 역시 최대 한 마리의 소만 도와줄 수 있다. 도움을 받을 수 있는 소가 최대 몇 마리인지 구해보자.
입력
첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.
출력
도움을 받을 수 있는 소가 최대 몇 마리인지 출력한다.
예제 입력 1
5 4 7 8 6 2 9 2 5 4 9 0 3 8 13
예제 출력 1
3
출처
Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Silver 1번
- 문제를 번역한 사람: jh05013
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호