Submission #124627

# Submission time Handle Problem Language Result Execution time Memory
124627 2019-07-03T15:39:36 Z arthurconmy Garage (IOI09_garage) C++14
100 / 100
5 ms 400 KB
// 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;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 4 ms 380 KB Output is correct
17 Correct 4 ms 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct