Submission #727964

#	Time	Username	Problem	Language	Result	Execution time	Memory
727964		Vlatko09	Garage (IOI09_garage)	C++14	0 / 100	1085 ms	468 KiB

garage

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> rates(n);
    for (int i = 0; i < n; i++) {
        cin >> rates[i];
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> arrivals;
    vector<int> weights(m);
    for (int i = 0; i < 2 * m; i++) {
        int car;
        cin >> car;
        if (car > 0) {
            int weight;
            cin >> weight;
            weights[car - 1] = weight;
            arrivals.emplace(i, car - 1);
        } else {
            car = -car;
            int space = -1;
            int cost = 0;
            for (int j = 0; j < n; j++) {
                if (space < 0 || rates[j] < rates[space]) {
                    space = j;
                }
            }
            if (space >= 0) {
                cost = rates[space] * weights[car - 1];
            }
            cout << cost << endl;
        }
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> releases;
    vector<bool> occupied(n);
    int revenue = 0;
    while (!arrivals.empty()) {
        auto [time, car] = arrivals.top();
        arrivals.pop();
        int space = -1;
        for (int i = 0; i < n; i++) {
            if (!occupied[i] && (space < 0 || rates[i] < rates[space])) {
                space = i;
            }
        }
        if (space >= 0) {
            occupied[space] = true;
            revenue += rates[space] * weights[car];
            releases.emplace(time + n, space);
        } else {
            arrivals.emplace(time + 1, car);
        }
    }
    while (!releases.empty()) {
        auto [time, space] = releases.top();
        releases.pop();
        occupied[space] = false;
    }
    cout << revenue << endl;
    return 0;
}

Compilation message (stderr)

garage.cpp: In function 'int main()':
garage.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [time, car] = arrivals.top();
      |              ^
garage.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         auto [time, space] = releases.top();
      |              ^

• Subtask 1: 0 / 100