Submission #1285647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285647		hayford08	Garage (IOI09_garage)	C++20	100 / 100	2 ms	576 KiB

garage

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

constexpr int INF = 1e9;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> rates(n);
  for (int &r : rates) {
    cin >> r;
  }
  vector<int> weights(m);
  for (int &w : weights) {
    cin >> w;
  }
  vector<int> arrivals(m * 2);
  for (int &a : arrivals) {
    cin >> a;
  }
  set<int> garage;
  for (int i = 0; i < n; i++) garage.insert(i);
  vector<int> spaceUsed(m, -INF);
  int ans = 0;
  queue<int> q;

  for (int car : arrivals) {
    if (car < 1) {
      int g = spaceUsed[abs(car) - 1];
      garage.insert(g);
    }
    else {
      q.push(car - 1);
    }
    while (garage.size() && q.size()) {
      int g = *garage.begin(); garage.erase(garage.begin());
      int curr = q.front(); q.pop();
      ans += weights[curr] * rates[g];
      spaceUsed[curr] = g;
    }
  }
  printf("%d\n", ans);

}

• Subtask 1: 100 / 100