Submission #493852

#	Time	Username	Problem	Language	Result	Execution time	Memory
493852		ahmeteren	Garage (IOI09_garage)	C++17	100 / 100	2 ms	464 KiB

garage

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

#define ll long long
const int N = 1e5 + 5;

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

	// #ifndef ONLINE_JUDGE
	// 	freopen("in.txt", "r", stdin);
	// 	freopen("out.txt", "w", stdout);
	// #endif

	ll n, m;
	cin >> n >> m;

	vector<ll> c(n + 1), w(m + 1);

	for(int i = 1; i <= n; i++)
		cin >> c[i];
	for(int i = 1; i <= m; i++)
		cin >> w[i];

	ll cevap = 0;
	map<ll, ll> mp;
	set<ll> st;
	queue<ll> q;

	for(int i = 1; i <= n; i++)
		st.insert(i);

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

		if(x > 0)
		{
			if(st.size())
			{
				ll a = *st.begin();
				cevap += w[x] * c[a];
				mp[x] = a;
				st.erase(st.begin());
			}
			else
			{
				q.push(x);
			}
		}
		else
		{
			x = -x;
			st.insert(mp[x]);
			if(q.size())
			{
				ll a = q.front(), b = *st.begin();
				q.pop();

				mp[a] = b;
				cevap += w[a] * c[b];
				st.erase(st.begin());
			}
		}
	}

	cout << cevap << '\n';
	return 0;
}

• Subtask 1: 100 / 100