Submission #1012083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012083		deera	Garage (IOI09_garage)	C++14	40 / 100	2 ms	604 KiB

garage

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    // freopen("2009/garage.txt", "r", stdin);

    ll n, m;
    cin >> n >> m;

    vector<ll> places(n);

    for (int i = 0; i < n; i++)
        cin >> places[i];

    vector<ll> weights(m);

    for (int i = 0; i < m; i++)
        cin >> weights[i];

    ll total = 0;
    queue<ll> waiting;
    priority_queue<pair<ll, ll>> avail;
    map<ll, ll> booked;

    for (int i = 0; i < n; i++) {
        avail.push({-i, i});
    }

    for (int i = 0; i < m*2; i++) {
        ll car;
        cin >> car;

        if (car < 0) {
            car = -car;
            car--;

            ll place = booked[car];
            avail.push({-place, place});
        } else {
            car--;
            waiting.push(car);
        }

        while (avail.size() != 0 && waiting.size() != 0) {
            ll next = waiting.front();
            waiting.pop();

            ll weight = weights[next];

            pair<ll, ll> spot = avail.top();
            avail.pop();
            ll rate = places[spot.second];

            booked[car] = spot.second;

            total += rate * weight;
        }
    }

    cout << total;

}

• Subtask 1: 40 / 100