| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 87 | 39 | 31 | 64.583% |
네모네모, 네모네모 sign 삐뚤빼뚤해 like
재우는 네모 네모 게임이라는 게임을 즐겨 한다.
네모 네모 게임은 가로 $M$칸, 세로 1ドル$칸의 격자판 위에 $N$개의 블록을 놓는 게임이다.
격자의 각 칸은 비어 있거나 X 표시가 되어 있다. X 표시가 되어 있는 칸 위에는 블록을 놓을 수 없다.
$i$번째 블록은 격자 위 가로로 $A_i$칸, 세로로 1ドル$칸의 공간을 차지한다.
또한, 블록은 순서대로 왼쪽부터 배치해야 한다. 즉, $i$번째 블록은 $i-1$번째 블록의 오른쪽에 놓여야 한다.
블록은 겹칠 수 없다. 즉, 한 칸의 격자 위에는 최대 한 개의 블록만이 놓일 수 있다.
이러한 조건을 만족하면서 $N$개의 블록을 모두 격자판 위에 올릴 경우 게임에서 승리한다.
이 게임에서 승리하도록 블록을 배치하는 경우의 수는 매우 많다. 재우는 이 게임을 좀 더 고능하게 하기 위해서 항상 블록이 놓이는 칸들을 구하려고 한다.
재우를 대신하여 항상 블록이 놓이는 칸의 개수를 구해주자.
첫 번째 줄에 블록 개수 $N,ドル 격자판의 가로 길이 $M,ドル X 표시된 칸의 수 $K$가 공백으로 구분되어 주어진다.
두 번째 줄에 각 블록의 가로 길이를 나타내는 $N$개의 정수 $A_1, A_2, \cdots , A_N$가 공백으로 구분되어 주어진다.
세 번째 줄에 X 표시된 칸들의 번호를 나타내는 $K$개의 정수 $X_1, X_2, \cdots , X_K$ ($i < j$ 이면 $X_i < X_j$)가 공백으로 구분되어 주어진다.
항상 조건을 만족하도록 블록을 배치할 방법이 있는 입력만 주어진다.
첫 번째 줄에 항상 블록이 놓이는 칸의 개수를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | 1ドル \le N, K \le 10,ドル 2ドル \le M \le 10$ |
| 2 | 11 | $A_i = 1$ |
| 3 | 27 | 1ドル \le N, K \le 10^3,ドル 2ドル \le M \le 10^3$ |
| 4 | 37 | 2ドル \le M \le 10^6$ |
| 5 | 16 | 추가 제약 조건 없음. |
2 6 1 2 2 3
3
4 10 1 1 1 3 3 7
5
5 11 3 1 1 1 1 1 4 5 11
0
School > 경기과학고등학교 > IamCoder Qualification Test > 2025 IamCoder Qualification Test C번