oj.uz

답안 #440813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440813 2021-07-03T08:53:39 Z dynam1c Garage (IOI09_garage) C++17
100 / 100
 2 ms 332 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<int> rr(n), ww(m), pp(m);
	for (int i = 0; i < n; i++)
		cin >> rr[i];
	for (int i = 0; i < m; i++)
		cin >> ww[i];
	vector<bool> park(n), inq(m);
	queue<int> q;
	ll res = 0;
	for (int qq = 0; qq < 2*m; qq++) {
		int e;
		cin >> e;
		if (e > 0) {
			e--;
			bool parked = false;
			for (int i = 0; i < n; i++)
				if (!park[i]) {
					parked = true;
					res += rr[i] * ww[e];
					pp[e] = i;
					park[i] = true;
					break;
				}
			if (!parked)
				q.push(e), inq[e] = true;
		} else {
			e = -e - 1;
			inq[e] = false;
			park[pp[e]] = false;
			while (!q.empty() and !inq[q.front()]) q.pop();
			if (!q.empty()) {
				int x = q.front(); q.pop();
				park[pp[e]] = true;
				res += rr[pp[e]] * ww[x];
				pp[x] = pp[e];
			}
		}
	}
	cout << res << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct