oj.uz

답안 #433922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433922 2021-06-20T12:15:15 Z rainboy Garage (IOI09_garage) C
100 / 100
 1 ms 332 KB 
#include <stdio.h>

#define N	100
#define M	2000

int iq[1 + N], pq[N], cnt;

int lt(int i, int j) { return i < j; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	static int rr[N], ww[M], ii[M], qu[M];
	int n, m, h, i, j, head, cnt_, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &rr[i]);
		pq_add(i);
	}
	for (j = 0; j < m; j++)
		scanf("%d", &ww[j]);
	head = cnt_ = 0;
	for (h = 0; h < m * 2; h++) {
		scanf("%d", &j);
		if (j > 0) {
			j--;
			if (cnt)
				ii[j] = pq_remove_first();
			else
				qu[head + cnt_++] = j;
		} else {
			j = -j - 1;
			if (cnt_)
				ii[qu[cnt_--, head++]] = ii[j];
			else
				pq_add(ii[j]);
		}
	}
	ans = 0;
	for (j = 0; j < m; j++)
		ans += ww[j] * rr[ii[j]];
	printf("%d\n", ans);
	return 0;
}

Compilation message

garage.c: In function 'main':
garage.c:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
garage.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d", &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~
garage.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d", &ww[j]);
      |   ^~~~~~~~~~~~~~~~~~~
garage.c:56:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d", &j);
      |   ^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 276 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 1 ms 280 KB Output is correct
9 Correct 1 ms 280 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 284 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 280 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 288 KB Output is correct
20 Correct 1 ms 332 KB Output is correct