Submission #1285647

#TimeUsernameProblemLanguageResultExecution timeMemory
1285647hayford08Garage (IOI09_garage)C++20
100 / 100
2 ms576 KiB
#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);

}
#Verdict Execution timeMemoryGrader output
Fetching results...