32001번 - Heat Stroke 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 76 | 11 | 9 | 15.000% |
문제
JOI Island consists of $L$ districts, numbered from $1$ to $L$ from west to east. There are $L -1$ roads in the island, numbered from $1$ to $L - 1$. Road $i$ ($1 ≤ i ≤ L - 1$) connects districts $i$ and $i + 1$ bidirectionally.
Now, the International Olympiad in Informatics (IOI 20XX) is planned to be held in JOI Island! The concern is that the island is famous for its extreme heat. There is a high risk of heat stroke, especially for foreign contestants who are not acclimatized to hot environment. So the organizers of IOI decided to take the following measures:
- First, for each $i$ ($1 ≤ i ≤ L$), they prepare a hospital at district $i$ with capacity of $C_i$ people. Note that there are cases that $C_i = 0$.
- During the IOI event, when a person on road $x$ ($1 ≤ x ≤ L - 1$) gets heat stroke, they send to hospital in the following procedure:
- They send the patient to the hospital of either district $x$ or $x + 1$, whichever is not full. If both hospitals are not full, either choice is possible. If both hospital are full, they send the patient to a general hospital outside the island by helicopter.
Since the usage of helicopter is costly, the organizers want to estimate the maximum number of patients to be sent by helicopter. They consider the following scenario as an example:
- Before the IOI event, there are no patients in any hospital.
- During the IOI event, $N$ people will get heat stroke in JOI Island. The $j$-th ($1 ≤ j ≤ N$) patient occurs on road $X_j$.
- For each $j$ ($1 ≤ j ≤ N - 1$), when the $(j + 1)$-th patient gets heat stroke, the $j$-th patient and earlier is already sent to hospital. Due to the severe symptoms of heat stroke, no patients leave hospital during the IOI event.
Write a program which, given the number of districts and the information of hospitals and heat stroke patients, computes the maximum number of patients to be sent by helicopter in the scenario above.
입력
Read the following data from the standard input.
$L$
$C_1$ $C_2$ $\cdots$ $C_L$
$N$
$X_1$ $X_2$ $\cdots$ $X_N$
출력
Write one line to the standard output. The output should contain the maximum number of patients to be sent by helicopter.
제한
- $2 ≤ L ≤ 8\, 000$.
- $0 ≤ C_i ≤ 8\, 000$ ($1 ≤ i ≤ L$).
- $1 ≤ N ≤ 8\, 000$.
- $1 ≤ X_j ≤ L - 1$ ($1 ≤ j ≤ N$).
- Given values are all integers.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $X_1 ≤ X_2 ≤ \cdots ≤ X_N$. |
| 2 | 7 | $L ≤ 18$, $N ≤ 18$, $C_i = 1$ ($1 ≤ i ≤ L$). |
| 3 | 7 | $L ≤ 18$, $N ≤ 100$, $C_i = 1$ ($1 ≤ i ≤ L$). |
| 4 | 25 | $L ≤ 100$, $N ≤ 100$, $C_i = 1$ ($1 ≤ i ≤ L$). |
| 5 | 25 | $L ≤ 100$, $N ≤ 100$. |
| 6 | 10 | $L ≤ 600$, $N ≤ 600$. |
| 7 | 15 | $L ≤ 3\, 500$, $N ≤ 3\, 500$. |
| 8 | 5 | No additional constraints. |
예제 입력 1
3 1 1 1 3 1 2 2
예제 출력 1
1
If the following case happens, $1$ patient will be sent by helicopter.
- Send the $1$st patient to the hospital at district $2$. Then, the number of patients in hospital at district $1$, $2$, $3$ will be $0$, $1$, $0$, respectively.
- Send the $2$nd patient to the hospital at district $3$. Then, the number of patients in hospital at district $1$, $2$, $3$ will be $0$, $1$, $1$, respectively.
- For the $3$rd patient, since both hospitals at district $2$ and $3$ are full, send the patient to a general hospital outside the island by helicopter.
Since there are no cases that $2$ or more patients will be sent by helicopter, output $1$.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 6, 7, 8.
예제 입력 2
6 1 1 1 1 1 1 7 1 3 5 4 2 2 3
예제 출력 2
3
If the following case happens, $3$ patient will be sent by helicopter.
- Send the $1$st patient to the hospital at district $2$. Then, the number of patients in hospital at district $1$, $2$, $3$, $4$, $5$, $6$ will be $0$, $1$, $0$, $0$, $0$, $0$, respectively.
- Send the $2$nd patient to the hospital at district $4$. Then, the number of patients in hospital at district $1$, $2$, $3$, $4$, $5$, $6$ will be $0$, $1$, $0$, $1$, $0$, $0$, respectively.
- Send the $3$rd patient to the hospital at district $5$. Then, the number of patients in hospital at district $1$, $2$, $3$, $4$, $5$, $6$ will be $0$, $1$, $0$, $1$, $1$, $0$, respectively.
- For the $4$th patient, since both hospitals at district $4$ and $5$ are full, send the patient to a general hospital outside the island by helicopter.
- Send the $5$th patient to the hospital at district $3$. Then, the number of patients in hospital at district $1$, $2$, $3$, $4$, $5$, $6$ will be $0$, $1$, $1$, $1$, $1$, $0$, respectively.
- For the $6$th patient, since both hospitals at district $2$ and $3$ are full, send the patient to a general hospital outside the island by helicopter.
- For the $7$th patient, since both hospitals at district $3$ and $4$ are full, send the patient to a general hospital outside the island by helicopter.
Since there are no cases that $4$ or more patients will be sent by helicopter, output $3$.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.
예제 입력 3
6 4000 1 1 0 4000 1 5 1 1 2 3 5
예제 출력 3
1
This sample input satisfies the constraints of Subtasks 1, 5, 6, 7, 8.
예제 입력 4
5 1 2 2 2 1 8 2 3 2 1 4 1 2 3
예제 출력 4
2
This sample input satisfies the constraints of Subtasks 5, 6, 7, 8.
예제 입력 5
10 2 2 2 2 2 2 2 2 2 2 18 1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8
예제 출력 5
3
This sample input satisfies the constraints of Subtasks 5, 6, 7, 8.
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호