Submission #1336441

#TimeUsernameProblemLanguageResultExecution timeMemory
1336441zhehanBikeparking (EGOI24_bikeparking)C++20
100 / 100
141 ms12272 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> ii;

signed main() {
  int n;
  cin >> n;
  vector<int> x(n, 0), y(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> y[i];
  }
  stack<ii> available_seats;
  available_seats.emplace(x[0], 0);
  int ans = 0;
  for (int i = 1; i < n; ++i) {
    while (y[i] > 0 && !available_seats.empty()) {
      int t = min(y[i], available_seats.top().first);
      y[i] -= t;
      ans += t;
      available_seats.top().first -= t;
      if (available_seats.top().first == 0) {
        available_seats.pop();
      }
    }
    available_seats.emplace(x[i], i);
  }
  vector<int> leftover(n, 0);
  while (!available_seats.empty()) {
    leftover[available_seats.top().second] = available_seats.top().first;
    available_seats.pop();
  }
  for (int i = 0; i < n; ++i) {
    y[i] -= min(y[i], leftover[i]);
    ans -= y[i];
  }
  cout << ans << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...