Submission #1232387

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

garage

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

void solve() {
    int n, m; cin >> n >> m;
    vector<ll> r(n), w(m), in(w);
    set<ll> avail;
    for (int i = 0; i < n; i++) cin >> r[i], avail.insert(i);
    for (int i = 0; i < m; i++) cin >> w[i];

    ll ans = 0;
    queue<ll> wait;
    for (int i = 0; i < 2 * m; i++) {
        ll x; cin >> x;

        if (x > 0) {
            if (avail.empty()) {
                wait.push(x);
            } else {
                ll y = *avail.begin();
                avail.erase(y);
                ans += w[x-1] * r[y];
                in[x-1] = y;
            }
        } else {
            x *= -1;
            ll y = in[x-1];
            avail.insert(y);

            while (!wait.empty()) {
                x = wait.front(); wait.pop();
                ll y = *avail.begin();
                avail.erase(y);
                ans += w[x-1] * r[y];
                in[x-1] = y;
            }
        }
    }

    cout << ans << endl;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 40 / 100