1350: Парковка


Відправити розв'язок


Бали:5
Time limit:0.5s
Memory limit:63M
Author:

Problem type

Парковка має n місць, пронумерованих від 1 до n включно. Парковка відкривається порожньою щоранку і працює протягом дня наступним чином. Коли автомобіль приїжджає на парковку, паркувальник перевіряє, чи є вільні місця. Якщо таких немає, автомобіль чекає біля в'їзду до тих пір, поки звільниться якесь місце. Якщо є вільне місце, або як тільки воно звільняється, автомобіль займає вільне місце для паркування. Якщо є кілька вільних паркувальних місць, автомобіль займає місце з найменшим номером. Коли приїжджають паркуватися інші автомобілі, але вже є автомобіль, що очікує, вони шикуються в чергу на в'їзді в тому порядку, в якому приїхали. Після того, як звільняється паркувальне місце, його займає перший автомобіль з черги (тобто той, який прибув паркуватися першим).

Вартість паркування одного автомобіля в доларах визначається як добуток маси цього автомобіля в кілограмах на тариф його паркувального місця. Вартість паркування автомобіля не залежить від того, скільки часу цей автомобіль знаходиться на парковці. Паркувальник знає, що сьогодні на парковку приїде m автомобілів, і він знає порядок їх приїзду та від'їзду. Допоможіть йому підрахувати, скільки доларів він заробить сьогодні.

Напишіть програму, яка за заданими тарифами паркувальних місць, ваги автомобілів та порядку, в якому автомобілі приїжджають і виїжджають, визначає прибуток паркувальника в доларах.

Формат вхідних даних

Перший рядок містить два цілі числа - кількість паркувальних місць n (1 ≤ n ≤ 100) та кількість автомобілей m (1 ≤ m ≤ 2,000), розділених проміжком.

Наступні n рядків описують тарифи паркувальних місць, s-ий з цих рядків містить одне ціле число rs (1 ≤ rs ≤ 100) – тариф паркувального місця з номером s в доларах за кілограм.

Наступні m рядків описують маси автомобілів. Автомобілі пронумеровані в довільному порядку від 1 до m включно, k-ий з цих m рядків містить одне ціле число wk (1 ≤ wk ≤ 10,000) – масу автомобіля з номером k в кілограмах.

Наступні 2m рядків описують приїзд та виїзд усіх автомобілів в хронологічному порядку. Додатне ціле число i показує, що автомобіль з номером i приїжджає на парковку. Від'ємне ціле число -i показує, що автомобіль з номером i їде з парковки. Жодний автомобіль не виїжджає з парковки до свого приїзду, і всі автомобілі від 1 до m включно з'являться в цій послідовності рядків рівно 2 рази, один раз як приїжджає, а другий - як виїжджає. До того ж, жоден з автомобілів не виїде з парковки, поки не займе місце на парковці (тобто, жодний автомобіль не виїде поки стоїть в черзі).

Формат вихідних даних

Одне ціле число - загальна кількість доларів, яку заробить сьогодні паркувальник.

Приклад вхідних даних

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

Приклад вихідних даних

5300

Коментарі


  • 0
    XEOL
     прокоментував о Травень 26, 2018

    Тести не відповідають умові!


    • 0
      zvit
       прокоментував о Травень 29, 2018 редагувати 2

      Які підозри є щодо тестів? Перевірив кількість вхідних рядків - все відповідно умові.