Submission #124627

#	Time	Username	Problem	Language	Result	Execution time	Memory
124627		arthurconmy	Garage (IOI09_garage)	C++14	100 / 100	5 ms	400 KiB

garage

// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)
int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	int n,m;
	cin>>n>>m;

	vi rate = {-1};

	REP(i,1,n)
	{
		int r;
		cin>>r;
		rate.push_back(r);
	}

	vi weight={-1};

	REP(i,1,m)
	{
		int w;
		cin>>w;
		weight.push_back(w);
	}

	priority_queue<int,vector<int>,greater<int>> avail;
	queue<int> wait;

	REP(i,1,n) avail.push(i);

	int ans=0;
	vi in_gar(max(n,m)+1);

	REP(i,1,2*m)
	{
		int cur;
		cin>>cur;

		if(cur<0)
		{
			avail.push(in_gar[-cur]);
			if(!wait.empty())
			{
				ans+=rate[avail.top()]*weight[wait.front()];
				in_gar[wait.front()]=avail.top();
				wait.pop();
				avail.pop();
			}
		}

		else
		{
			if(avail.empty()) wait.push(cur);
			else
			{
				ans+=rate[avail.top()]*weight[cur];
				in_gar[cur]=avail.top();
				avail.pop();
			}
		}
	}

	cout << ans << endl;
}

• Subtask 1: 100 / 100