11666번 - 워크스테이션 배정 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 256 MB | 395 | 163 | 133 | 43.750% |
문제
찬솔이는 최근 새로 만들어진 슈퍼컴퓨터의 관리를 맡고 있다. 그의 업무는, 연구원들이 슈퍼컴퓨터로 계산을 하려 할 때마다 워크스테이션을 연구원들에게 배정해 주는 것이다.
여기까지는 좋은데, 찬솔이는 매우 게을러서 연구원들이 올 때마다 기계를 잠금 해제하는 것을 귀찮아하기 시작했다. 원격 조종도 가능하긴 한데 아무튼 귀찮은 모양이다. 결국 찬솔이는 보안 규정을 무시하고, 연구원들이 떠나기 전에 워크스테이션을 잠그고 떠나지 말아줄 것을 부탁하기로 했다. 이렇게 하면, 새 연구원들이 왔을 때 잠금이 풀린 빈 워크스테이션에 배정해주면 되니까, 훨씬 일이 덜 귀찮아질 것이다.
애석하게도, 빈 워크스테이션은 m분을 초과하는 시간동안 작업이 없을 때, 자동으로 잠겨진다. 즉 찬솔이가 귀찮게 다시 잠금을 풀어야 한다는 것을 뜻한다. 찬솔이는 각각의 연구원들의 슈퍼컴퓨터 사용 스케줄을 모두 가지고 있다. 찬솔이가 최적의 방법을 사용해서 워크스테이션을 배정한다면, 잠금 해제를 몇번 덜 할 수 있을까? 워크스테이션은 충분하다고 가정해도 괜찮다.
입력
입력은 다음과 같이 주어진다 :
- 첫 번째 줄에 연구원의 수 n (1 ≤ n ≤ 300 000), 워크스테이션이 자동으로 잠기는 기준 시간 m (1 ≤ m ≤ 108) 이 주어진다.
- n개의 줄에 a와 s가 주어진다. (1 ≤ a, s ≤ 108) 연구원들은 a분에 도착해서, 정확히 s분동안 머무른다.
출력
찬솔이가 절약할 수 있는 잠금 해제 횟수의 최댓값을 출력하라.
예제 입력 1
3 5 1 5 6 3 14 6
예제 출력 1
2
예제 입력 2
5 10 2 6 1 2 17 7 3 9 15 6
예제 출력 2
3
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2015 A번
- 문제를 번역한 사람: koosaga
- 문제를 만든 사람: Stefan Toman
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호