Submission #1177640

#TimeUsernameProblemLanguageResultExecution timeMemory
1177640qrnGarage (IOI09_garage)C++20
100 / 100
1 ms328 KiB
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 2e5 + 5;
const intt L = 21;

void solve() {
    intt N, M;
    cin >> N >> M;
    
    vector<intt> R(N), W(M), P(M);
    for(intt i = 0; i < N; i++) {
        cin >> R[i];
    }
    for(intt i = 0; i < M; i++) {
        cin >> W[i];
    }

    set<intt> st;
    queue<intt> q;
    for(intt i = 1; i <= N; i++) st.insert(i);

    intt profit = 0;
    for(intt i = 1; i <= 2 * M; i++) {
        intt car;
        cin >> car;
        if(car > 0) {
            q.push(car);
        } else {
            car = -car;
            st.insert(P[car]);
        }

        while(not st.empty() && not q.empty()) {
            P[q.front()] = *st.begin();
            profit += W[q.front() - 1] * R[*st.begin() - 1];
            q.pop();
            st.erase(st.begin());
        }
    }
    
    cout << profit << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...