---
tags: IOI
---
# IOI2009 Day2-1 車庫 (Garage)

やるだけ
難易度5

## 問題

https://www.ioi-jp.org/ioi/2009/problems/day2/Garage_jp.pdf
https://oj.uz/problem/view/IOI09_garage

$N$ 個の駐車スペースがあり、$M$ 台の車が出入りする。
入ってくる車は、空いている駐車スペースのうち最も番号が小さい場所に駐車する。
駐車スペースが空いていない場合は並んで待つ。
重さ $W$ の車が駐車スペース $i$ に駐車すると、 $W\times R_i$ の売り上げを得る。
売り上げの合計を求めよ。

## 実装

https://oj.uz/submission/220419

#include <bits/stdc++.h>
using namespace std;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
 
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> r(n), w(m);
    each(i, r) cin >> i;
    each(i, w) cin >> i;
    int ans = 0;
    vector<int> park(m);
    priority_queue<int, vector<int>, greater<int>> space;
    queue<int> q;
    rep(n) space.push(i);
    rep(m * 2){
        int a;
        cin >> a;
        if(a < 0){
            int at = park[~a];
            if(q.size()){
                a = q.front();
                q.pop();
                park[a] = at;
                ans += r[at] * w[a];
            }
            else space.push(at);
        }
        else{
            a--;
            if(space.size()){
                int at = space.top();
                space.pop();
                park[a] = at;
                ans += r[at] * w[a];
            }
            else q.push(a);
        }
    }
    cout << ans << endl;
}