18855번 - Treatment Project 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 76 | 46 | 29 | 54.717% |
문제
There are N houses in the JOI kingdom, numbered from 1 to N. The houses lie on a line in numerical order. A citizen lives in each house. The citizen living in the house x (1 ≤ x ≤ N) is denoted by the citizen x.
Recently, new virus appeared, and every citizen was infected with the virus. In order to deal with the problem, M treatment projects are proposed. The cost of the project i (1 ≤ i ≤ M) is Ci. If the project i is performed, the following happens:
In the evening of the Ti-th day, if the citizen x with Li ≤ x ≤ Ri is infected with the virus, then the citizen x is treated.
The virus is transmitted through the neighboring citizens in the following way.
If the citizen x (1 ≤ x ≤ N) is infected with the virus in the morning of some day, then the citizen x − 1 (if x ≥ 2) and the citizen x + 1 (if x ≤ N − 1) become infected with the virus at noon of the same day.
A citizen who was already treated can be infected with the virus again.
Since you are a minister of the JOI kingdom, you need to choose some of the projects so that the following condition is satisfied.
Condition. After all the chosen projects are performed, no citizen is infected with the virus.
It is possible to perform more than one project on the same day.
Write a program which, given the number of houses and the information of the treatment projects, determines whether it is possible to satisfy the above condition, and calculates the minimum total cost if it is possible.
입력
Read the following data from the standard input. All the values in the input are integers.
N M T1 L1 R1 C1 . . . TM LM RM CM
출력
Write one line to the standard output. If the condition cannot be satisfied, output −1. Otherwise, output the minimum total cost.
제한
- 1 ≤ N ≤ 1 000 000 000.
- 1 ≤ M ≤ 100 000.
- 1 ≤ Ti ≤ 1 000 000 000 (1 ≤ i ≤ M).
- 1 ≤ Li ≤ Ri ≤ N (1 ≤ i ≤ M).
- 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | Ti = 1 (1 ≤ i ≤ M). |
| 2 | 5 | M ≤ 16. |
| 3 | 30 | M ≤ 5 000. |
| 4 | 61 | No additional constraints. |
예제 입력 1
10 5 2 5 10 3 1 1 6 5 5 2 8 3 7 6 10 4 4 1 3 1
예제 출력 1
7
In Sample Input 1, you can perform the projects as follows.
- In the evening of the second day, the project 1 is performed, and the citizens 5, 6, 7, 8, 9, 10 are treated. Now the citizens 1, 2, 3, 4 are infected with the virus.
- At noon of the third day, the citizen 5 becomes infected with the virus. Now the citizens 1, 2, 3, 4, 5 are infected with the virus.
- At noon of the fourth day, the citizen 6 becomes infected with the virus. Now the citizens 1, 2, 3, 4, 5, 6 are infected with the virus.
- In the evening of the fourth day, the project 5 is performed, and the citizens 1, 2, 3 are treated. Now the citizens 4, 5, 6 are infected with the virus.
- At noon of the fifth day, the citizens 3 and 7 become infected with the virus. Now the citizens 3, 4, 5, 6, 7 are infected with the virus.
- In the evening of the fifth day, the project 3 is performed, and the citizens 3, 4, 5, 6, 7 are treated. After that, no citizen is infected with the virus.
The total cost to perform the projects 1, 3 and 5 is 7. Since it is impossible to perform projects so that the condition is satisfied and the total cost is smaller than 7, output 7.
예제 입력 2
10 5 2 6 10 3 1 1 5 5 5 2 7 3 8 6 10 4 4 1 3 1
예제 출력 2
-1
In Sample Input 2, output −1 since the condition cannot be satisfied.
예제 입력 3
10 5 1 5 10 4 1 1 6 5 1 4 8 3 1 6 10 3 1 1 3 1
예제 출력 3
7
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호