oj.uz

Submission #796836

# Submission time Handle Problem Language Result Execution time Memory
796836 2023-07-28T19:35:22 Z pluto_ish Garage (IOI09_garage) C++14
100 / 100
 2 ms 340 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 224 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 312 KB Output is correct
20 Correct 2 ms 340 KB Output is correct