프로그램 명: ioi_garage
제한시간: 1 초
[문제요약]
주차장에 1에서 N까지 번호가 붙은 주차공간이 있습니다.
처음에는 모든 공간이 비어있습니다.
어떤 차가 주차장에 도착하면 비어있는 공간 중에 번호가 가장 작은 공간에 차를 배정합니다. 비어있는 공간이 없다면 차를 queue에 넣어서 비어지는 공간이 생길 때 까지 기다리게 합니다.
주차료는 차량의 무게에 비례합니다. 차량 k가 주차공간 s에 주차하게 되면
주차료는 Rs * Wk가 됩니다.
M개의 차가 들어오고 나간다는 것을 알때 주차장의 수익을 계산하는 문제입니다.
입력
입력은
첫째줄에 N과 M이 주어짐.
그다음 N개 줄에 R이 주어짐 s번째 줄에 Rs가 주어짐
그다음 M개 줄에 W가 주어짐 k번째 줄에 Wk가 주어짐
그다음 2*M개 줄에 차량의 주차장 출입 순서를 나타내는 정수가 주어짐
i는 차량 i가 주차장에 들어옴을 의미
-i는 차량 i가 주차장에서 나감을 의미
주차장에 들어오지 않은 차량 주차장에서 나가는 입력은 없음
1에서 M까지 모든 차량은 한번 들어오고 한번 나감
또한 queue에서 대기중인 차량이 나가게 되는 경우는 없음
출력
출력은 총 수익을 출력하면 됩니다.
A parking garage has N parking spaces, numbered from 1 to N inclusive. The garage opens
empty each morning and operates in the following way throughout the day. Whenever a car
arrives at the garage, the attendants check whether there are any parking spaces available. If
there are none, then the car waits at the entrance until a parking space is released. If a parking
space is available, or as soon as one becomes available, the car is parked in the available
parking space. If there is more than one available parking space, the car will be parked at the
space with the smallest number. If more cars arrive while some car is waiting, they all line up in a
queue at the entrance, in the order in which they arrived. Then, when a parking space becomes
available, the first car in the queue (i.e., the one that arrived the earliest) is parked there.
The cost of parking in dollars is the weight of the car in kilograms multiplied by the specific rate
of its parking space. The cost does not depend on how long a car stays in the garage.
The garage operator knows that today there will be M cars coming and he knows the order of
their arrivals and departures. Help him calculate how many dollars his revenue is going to be
today.
TASK
Write a program that, given the specific rates of the parking spaces, the weights of the cars and
the order in which the cars arrive and depart, determines the total revenue of the garage in
dollars.
CONSTRAINTS
1 ￡ N ￡ 100 The number of parking spaces
1 ￡ M ￡ 2,000 The number of cars
1 ￡ Rs ￡ 100 The rate of parking space s in dollars per kilogram
1 ￡ Wk ￡ 10,000 The weight of car k in kilograms
입력
Your program must read from standard input the following data:
· The first line contains the integers N and M, separated by a space.
· The next N lines describe the rates of the parking spaces. The sth of these lines contains a
single integer Rs, the rate of parking space number s in dollars per kilogram.
· The next M lines describe the weights of the cars. The cars are numbered from 1 to M
inclusive in no particular order. The kth of these M lines contains a single integer Wk, the
weight of car k in kilograms.
· The next 2*M lines describe the arrivals and departures of all cars in chronological order. A
positive integer i indicates that car number i arrives at the garage. A negative integer -i
indicates that car number i departs from the garage. No car will depart from the garage
before it has arrived, and all cars from 1 to M inclusive will appear exactly twice in this
sequence, once arriving and once departing. Moreover, no car will depart from the garage
before it has parked (i.e., no car will leave while waiting on the queue).
출력
Your program must write to standard output a single line containing a single integer: the total
number of dollars that will be earned by the garage operator today.
입출력 예
입력
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1
출력
5300
Car number 3 goes to space number 1 and pays 300 * 2 = 600 dollars.
Car number 2 goes to space number 2 and pays 100 * 3 = 300 dollars.
Car number 1 goes to space number 1 (which was released by car number 3) and pays 200 * 2
= 400 dollars.
Car number 4 goes to space number 3 (the last remaining) and pays 800 * 5 = 4,000 dollars.
입력
2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4
출력
16200
Car number 3 goes to space number 1 and pays 1,000 * 5 = 5,000 dollars.
Car number 1 goes to space number 2 and pays 100 * 2 = 200 dollars.
Car number 2 arrives and has to wait at the entrance.
Car number 4 arrives and has to wait at the entrance behind car number 2.
When car number 1 releases its parking space, car number 2 parks there and pays 500 * 2 =
1,000 dollars.
When car number 3 releases its parking space, car number 4 parks there and pays 2,000 * 5 =
10,000 dollars.
출처: International Olympiad In Informatics 2009
요약: august14
[질/답]
[제출 현황]
[푼 후(0)]