레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Garage
English 1.2
주차장 (GARAGE)
Full Feedback Problem
주차장에는 1부터 N까지 번호가 매겨진 N개의 주차 공간이 있다. 주차장은 매일 아침 빈 상태로 문을 열고 하루 종일 다음과 같이 운영된다. 차가 주차장에 도착할 때마다 관리인은 빈 주차 공간이 있는지 확인한다. 없으면 그 차는 주차 공간이 빌 때까지 입구에서 기다린다. 빈 주차 공간이 있으면, 또는 하나가 비는 즉시, 그 차는 빈 주차 공간에 주차된다. 빈 주차 공간이 여러 개이면 차는 번호가 가장 작은 공간에 주차된다. 어떤 차가 기다리는 동안 다른 차들이 도착하면, 도착한 순서대로 입구에 줄을 선다. 그 후 주차 공간이 비면 줄의 첫 번째 차(즉, 가장 먼저 도착한 차)가 그곳에 주차된다.
주차 요금(달러)은 차의 무게(킬로그램)에 그 주차 공간의 요율을 곱한 값이다. 요금은 차가 주차장에 머무는 시간과 무관하다.
주차장 운영자는 오늘 M대의 차가 올 것을 알고 있으며, 그들의 도착과 출발 순서도 알고 있다. 오늘 그의 수입이 몇 달러가 될지 계산하는 것을 도와주시오.
TASK
주차 공간들의 요율, 차들의 무게, 그리고 차들이 도착하고 출발하는 순서가 주어졌을 때, 주차장의 총수입을 달러 단위로 구하는 프로그램을 작성하시오.
EXAMPLES
Sample Input
Sample Output
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1
5300
3번 차가 1번 공간으로 가서 300 * 2 = 600달러를 낸다.
2번 차가 2번 공간으로 가서 100 * 3 = 300달러를 낸다.
1번 차가 (3번 차가 비운) 1번 공간으로 가서 200 * 2 = 400달러를 낸다.
4번 차가 (마지막으로 남은) 3번 공간으로 가서 800 * 5 = 4,000달러를 낸다.
Sample Input
Sample Output
2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4
16200
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Garage
English 1.2
3번 차가 1번 공간으로 가서 1,000 * 5 = 5,000달러를 낸다.
1번 차가 2번 공간으로 가서 100 * 2 = 200달러를 낸다.
2번 차가 도착하지만 입구에서 기다려야 한다.
4번 차가 도착하여 2번 차 뒤에서 기다려야 한다.
1번 차가 주차 공간을 비우면 2번 차가 그곳에 주차하고 500 * 2 = 1,000달러를 낸다.
3번 차가 주차 공간을 비우면 4번 차가 그곳에 주차하고 2,000 * 5 = 10,000달러를 낸다.
\(1 \le N \le 100\)
주차 공간의 수
\(1 \le M \le 2,000\)
차의 수
\(1 \le Rs \le 100\)
주차 공간 s의 킬로그램당 달러 요율
\(1 \le Wk \le 10,000\)
차 k의 무게(킬로그램)
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N과 M이 공백으로 구분되어 주어진다.
• 다음 N개의 줄에는 주차 공간들의 요율이 주어진다. 이 중 s번째 줄에는 s번 주차 공간의 킬로그램당 달러 요율인 정수 Rs 하나가 있다.
• 다음 M개의 줄에는 차들의 무게가 주어진다. 차에는 특별한 순서 없이 1부터 M까지 번호가 매겨져 있다. 이 M개의 줄 중 k번째 줄에는 차 k의 무게(킬로그램)인 정수 Wk 하나가 있다.
• 다음 2*M개의 줄에는 모든 차의 도착과 출발이 시간순으로 주어진다. 양의 정수 i는 i번 차가 주차장에 도착함을 나타낸다. 음의 정수 -i는 i번 차가 주차장에서 출발함을 나타낸다. 어떤 차도 도착하기 전에 출발하지 않으며, 1부터 M까지의 모든 차가 이 수열에 정확히 두 번(도착 한 번, 출발 한 번) 나타난다. 또한 어떤 차도 주차하기 전에 주차장을 떠나지 않는다(즉, 줄에서 기다리는 동안 떠나는 차는 없다).
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Garage
English 1.2
프로그램은 표준 출력에 정수 하나가 있는 한 줄을 출력해야 한다: 오늘 주차장 운영자가 벌게 될 총 달러 액수.
GRADING
40점에 해당하는 여러 테스트에서는 도착하는 모든 차에 대해 항상 빈 주차 공간이 적어도 하나 있다. 이 경우 어떤 차도 공간을 기다릴 필요가 없다.