Submission #796836

#	Time	Username	Problem	Language	Result	Execution time	Memory
796836		pluto_ish	Garage (IOI09_garage)	C++14	100 / 100	2 ms	340 KiB

garage

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> rate(n), wt(m);
	for(int& x : rate) cin >> x;
	for(int& x : wt) cin >> x;

	set<int> avlb;
	for(int i=1;i<=n;i++) avlb.insert(i);
	queue<int> wl;
	set<int> gone;
	vector<int> assigned(m, -1);
	long long cost = 0;
	for(int i=0;i<2*m;i++){
		int num; cin >> num;
		if(num > 0){
			if(avlb.empty()){
				wl.push(num);
			} else {
				assigned[num-1] = *avlb.begin();
				avlb.erase(avlb.begin());
				//cout << num << " assigned lot " << assigned[num-1] << " with cost " << rate[assigned[num-1]-1]*wt[num-1] << "\n";
				cost += rate[assigned[num-1]-1]*wt[num-1]; 
			}
		} else {
			num *= -1;
			if(assigned[num-1] != -1){
				avlb.insert(assigned[num-1]);
				while(!wl.empty()){
					num = wl.front();
					if(gone.find(num) == gone.end()) break;
					else wl.pop();
				}
				if(!wl.empty()){
					num = wl.front(); wl.pop();
					assigned[num-1] = *avlb.begin();
					avlb.erase(avlb.begin());
					//cout << num << " assigned lot " << assigned[num-1] << " with cost " << rate[assigned[num-1]-1]*wt[num-1] << "\n";
					cost += rate[assigned[num-1]-1]*wt[num-1];
				}
			} else {
				gone.insert(num);
			}
		}
	}
	cout << cost << "\n";
	return 0;
}

• Subtask 1: 100 / 100