Submission #297469

#	Time	Username	Problem	Language	Result	Execution time	Memory
297469		aryan12	Garage (IOI09_garage)	C++17	100 / 100	2 ms	512 KiB

garage

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

void Solve() {
	long long spaces, cars;
	cin >> spaces >> cars;
	long long cost[spaces + 1], weight[cars + 1];
	for(long long i = 1; i <= spaces; i++) {
		cin >> cost[i];
	}
	for(long long i = 1; i <= cars; i++) {
		cin >> weight[i];
	}
	unordered_map<long long, long long> Occupier;
	//  <car, space it has occupied>
	set<long long> SpacesLeft;
	for(long long i = 1; i <= spaces; i++) {
		SpacesLeft.insert(i);
	}
	long long TotalCost = 0;
	queue<long long> CarsWaiting;
	for(long long i = 1; i <= 2 * cars; i++) {
		long long operation;
		cin >> operation;
		if(operation > 0) {
			if(SpacesLeft.size() == 0) {
				CarsWaiting.push(operation);
			}
			else {
				set<long long> :: iterator itr;
				itr = SpacesLeft.begin();
				long long pos = *itr;
				Occupier[operation] = pos;
				SpacesLeft.erase(pos);
				TotalCost += (weight[operation] * cost[pos]);
			}
		}
		else {
			long long NewPos = Occupier[-operation];
			Occupier[-operation] = -1;
			if(CarsWaiting.empty())
				SpacesLeft.insert(NewPos);
			else {
				long long Car = CarsWaiting.front();
				Occupier[Car] = NewPos;
				TotalCost += (weight[Car] * cost[NewPos]);
				CarsWaiting.pop();
			}
		}
	}
	cout << TotalCost << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Solve();
	return 0;
}

• Subtask 1: 100 / 100