結果

問題 No.2006 Decrease All to Zero
ユーザー 👑 ygussanyygussany
提出日時 2022-06-26 15:47:25
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 817 ms / 4,000 ms
コード長 2,984 bytes
コンパイル時間 1,757 ms
コンパイル使用メモリ 32,428 KB
実行使用メモリ 12,840 KB
最終ジャッジ日時 2023-08-09 05:58:44
合計ジャッジ時間 8,446 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
12,112 KB
testcase_01 AC 2 ms
12,144 KB
testcase_02 AC 31 ms
12,484 KB
testcase_03 AC 3 ms
12,048 KB
testcase_04 AC 2 ms
12,128 KB
testcase_05 AC 0 ms
4,384 KB
testcase_06 AC 3 ms
12,048 KB
testcase_07 AC 3 ms
12,424 KB
testcase_08 AC 3 ms
11,980 KB
testcase_09 AC 3 ms
12,144 KB
testcase_10 AC 684 ms
12,176 KB
testcase_11 AC 816 ms
12,428 KB
testcase_12 AC 684 ms
12,204 KB
testcase_13 AC 686 ms
12,596 KB
testcase_14 AC 815 ms
12,268 KB
testcase_15 AC 817 ms
12,284 KB
testcase_16 AC 276 ms
12,176 KB
testcase_17 AC 625 ms
12,840 KB
testcase_18 AC 1 ms
4,384 KB
testcase_19 AC 0 ms
4,384 KB
testcase_20 AC 3 ms
12,080 KB
testcase_21 AC 2 ms
12,076 KB
testcase_22 AC 3 ms
12,184 KB
testcase_23 AC 3 ms
12,080 KB
testcase_24 AC 3 ms
12,164 KB
testcase_25 AC 3 ms
12,108 KB
testcase_26 AC 684 ms
12,792 KB
testcase_27 AC 35 ms
12,456 KB
testcase_28 AC 36 ms
12,552 KB
testcase_29 AC 15 ms
12,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <stdio.h>
#include <stdlib.h>

const long long sup = 1LL << 60;

typedef struct {
	long long key;
	int id;
} data;

typedef struct {
	data obj[100001];
	int size;
} min_heap;

void push(min_heap* h, data x)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key < h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j <<= 1;
		} else break;
	}
	return output;
}

long long solve(int N, int X[], int A[])
{
	if (N == 1) {
		if (A[1] == 1) return 0;
		else return -1;
	}
	
	int i, D[201], A_max = 0;
	for (i = 2; i <= N; i++) D[i] = X[i] - X[i-1];
	for (i = 1; i <= N; i++) if (A_max < A[i]) A_max = A[i];
	A_max *= 2;
	
	int j, jj, k, kk, kkk, cur, prev, L[100001], R[100001], tail;
	long long dp[2][3][10001], tmp, Y[100001];
	data d;
	min_heap h[3][2], hh;
	for (j = 0; j <= 2; j++) for (k = 0; k <= A_max; k++) dp[0][j][k] = sup;
	dp[0][0][A[1]*2] = 0;
	dp[0][1][A[1]*2-1] = 0;
	dp[0][2][A[1]*2-2] = 0;
	for (i = 2, cur = 1, prev = 0; i <= N; i++, cur ^= 1, prev ^= 1) {
		for (j = 0, tail = 0; j <= 2; j++) for (k = 0; k <= 1; k++) h[j][k].size = 0;
		for (j = 0; j <= 2; j++) {
			for (k = 1; k <= A_max; k++) {
				if (dp[prev][j][k] == sup) continue;
				tmp = dp[prev][j][k] + (long long)k * D[i];
				for (jj = 0; jj <= 2 - j; jj++) {
					Y[tail] = tmp;
					kk = A[i] * 2 - jj;
					kkk = 0;
					R[tail] = k + kk - kkk;
					kkk = A[i] * 2 - jj;
					if (kkk > k) kkk = k;
					kk = A[i] * 2 - jj - kkk;
					L[tail] = k + kk - kkk;
					d.key = L[tail];
					d.id = tail;
					push(&(h[j+jj][abs(L[tail])%2]), d);
					tail++;
				}
			}
		}
		
		for (j = 0; j <= 2; j++) {
			for (k = 0, hh.size = 0; k <= A_max; k += 2) {
				while (h[j][0].size > 0 && h[j][0].obj[1].key <= k) {
					d = pop(&(h[j][0]));
					d.key = Y[d.id];
					push(&hh, d);
				}
				while (hh.size > 0 && R[hh.obj[1].id] < k) pop(&hh);
				if (hh.size > 0) dp[cur][j][k] = hh.obj[1].key;
				else dp[cur][j][k] = sup;
			}
			for (k = 1, hh.size = 0; k <= A_max; k += 2) {
				while (h[j][1].size > 0 && h[j][1].obj[1].key <= k) {
					d = pop(&(h[j][1]));
					d.key = Y[d.id];
					push(&hh, d);
				}
				while (hh.size > 0 && R[hh.obj[1].id] < k) pop(&hh);
				if (hh.size > 0) dp[cur][j][k] = hh.obj[1].key;
				else dp[cur][j][k] = sup;
			}
		}
	}
	if (dp[prev][2][0] == sup) return -1;
	else return dp[prev][2][0];
}

int main()
{
	int i, N, X[201], A[201], A_max = 0;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(X[i]));
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));
	printf("%lld\n", solve(N, X, A));
	fflush(stdout);
	return 0;
}
0