結果

問題 No.2006 Decrease All to Zero
コンテスト
ユーザー 👑 ygussany
提出日時 2022-06-26 15:47:25
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 843 ms / 4,000 ms
コード長 2,984 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 33,508 KB
実行使用メモリ 13,152 KB
最終ジャッジ日時 2024-11-14 11:48:10
合計ジャッジ時間 7,867 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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