Submission #601053

# Submission time Handle Problem Language Result Execution time Memory
601053 2022-07-21T10:39:11 Z SlyGaleeb Garage (IOI09_garage) C++17
100 / 100
2 ms 360 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ld long double
#define F first
#define S second
const ll N = 2e5 + 5;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,ans=0;
    cin >> n >> m;
    vector<int>v(n+1),w(m+1);
    priority_queue<int,vector<int>,greater<int>>pq;
    queue<int>q;
    map<int,int>mp;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        pq.push(i);
    }
    for (int i = 1; i <= m; ++i)
        cin >> w[i];
    for (int i = 0; i < 2*m; ++i) {
        while (!q.empty() && !pq.empty()) {
            ans += w[q.front()]*v[pq.top()];
            mp[q.front()] = pq.top();
            q.pop();
            pq.pop();
        }
        int a;
        cin >> a; 
        if (a>0) {
            if (pq.empty())
                q.push(a);
            else {
                ans += w[a]*v[pq.top()];
                mp[a] = pq.top();
                pq.pop();
            }
        }
        else {
            pq.push(mp[-a]);
            mp.erase(-a);
        }
    }
    cout << ans;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 352 KB Output is correct
20 Correct 2 ms 360 KB Output is correct