Submission #933630

#	Time	Username	Problem	Language	Result	Execution time	Memory
933630		Neytrino	Garage (IOI09_garage)	C++14	100 / 100	3 ms	464 KiB

garage

	/**
	*    author:    inastranets
	*    created:   26.02.2024 01:14:14		
	**/
	#include <bits/stdc++.h>

	using namespace std;

	const int UNDEF = -1;
	const int TAKED = INT_MAX; 

	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(0);

		int n, m;

		cin >> n >> m;

		vector<int> price(n+1);
		vector<int> weight(m+1);
		vector<int> line(2 * m + 1);
		vector<int> garage(n+1, UNDEF);

		for (int i = 1; i <= n; ++ i) cin >> price[i];
		for (int j = 1; j <= m; ++ j) cin >> weight[j];
		for (int k = 1; k <= 2 * m; ++ k) cin >> line[k];

		long long ans = 0;

		for (int k = 1; k <= 2 * m; ++ k) {
			if (line[k] > 0 && line[k] != TAKED) {
				bool found = false;
				for (int i = 1; i <= n && !found; ++ i) {
					if (garage[i] == UNDEF) {
						garage[i] = line[k];
						ans += price[i] * weight[line[k]];
						found = true;
					} 
				}

				if (!found) {
					int i;
					for (i = k + 1; i <= 2 * m; ++ i) {
						if (line[i] < 0) {	
							break;
						}
					}

					line[i] = -line[i];
					
					for (int j = 1; j <= n; ++ j) {
						if (line[i] == garage[j]) {
							ans += weight[line[k]] * price[j];
							garage[j] = line[k];
							line[i] = TAKED;
							break;
						}
					}
				}

			} else {
				line[k] = -line[k];
				for (int i = 1; i <= n; ++ i) {
					if (line[k] == garage[i]) {
						garage[i] = UNDEF;
						break;
					}
				}	
			}
		}

		cout << ans;
		
		return 0;
	}	

• Subtask 1: 100 / 100