Logo
(追記) (追記ここまで)

32001번 - Heat Stroke 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB7611915.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.

서브태스크

번호배점제한
16

$X_1 ≤ X_2 ≤ \cdots ≤ X_N$.

27

$L ≤ 18,ドル $N ≤ 18,ドル $C_i = 1$ (1ドル ≤ i ≤ L$).

37

$L ≤ 18,ドル $N ≤ 100,ドル $C_i = 1$ (1ドル ≤ i ≤ L$).

425

$L ≤ 100,ドル $N ≤ 100,ドル $C_i = 1$ (1ドル ≤ i ≤ L$).

525

$L ≤ 100,ドル $N ≤ 100$.

610

$L ≤ 600,ドル $N ≤ 600$.

715

$L ≤ 3,円 500,ドル $N ≤ 3,円 500$.

85

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.

  1. 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.
  2. 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.
  3. 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.

힌트

출처

Contest > JOI Open Contest > JOI Open Contest 2024 2번

채점 및 기타 정보

  • 예제는 채점하지 않는다.
(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /