Submission #1245603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245603		gmalex98	Garage (IOI09_garage)	C++20	100 / 100	1 ms	328 KiB

garage

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

int main() {
    int n, m, res = 0;
    cin >> n >> m;

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

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

    priority_queue<int, vector<int>, greater<int>> free_spots;
    for (int i = 0; i < n; ++i) free_spots.push(i);

    queue<int> waiting;
    unordered_map<int, int> parked;

    for (int i = 0; i < 2 * m; ++i) {
        int x;
        cin >> x;
        if (x > 0) {
            x--; // 0-based
            if (!free_spots.empty()) {
                int spot = free_spots.top(); free_spots.pop();
                res += weights[x] * rates[spot];
                parked[x] = spot;
            } else {
                waiting.push(x);
            }
        } else {
            x = -x - 1;
            if (parked.find(x) == parked.end()) {
                continue; // skip auto koji nije parkiran
            }
            int spot = parked[x];
            parked.erase(x);
            if (!waiting.empty()) {
                int next = waiting.front(); waiting.pop();
                res += weights[next] * rates[spot];
                parked[next] = spot;
            } else {
                free_spots.push(spot);
            }
        }
    }

    cout << res << '\n';
}

• Subtask 1: 100 / 100