結果

問題 No.2006 Decrease All to Zero
ユーザー to-omerto-omer
提出日時 2022-07-01 18:28:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,166 ms / 4,000 ms
コード長 2,186 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 101,536 KB
最終ジャッジ日時 2024-11-14 11:48:01
合計ジャッジ時間 13,760 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.buffer.readline
INF = 10 ** 18
class QueueAggregation:
def __init__(self, e, f):
self.e = e
self.f = f
self.front = []
self.back = []
def fold_all(self):
return self.f(
self.front[-1][0] if self.front else self.e,
self.back[-1][0] if self.back else self.e,
)
def append(self, val):
x = self.f(
self.back[-1][0] if self.back else self.e,
val,
)
self.back.append((x, val))
def appendleft(self, val):
x = self.f(
val,
self.front[-1][0] if self.front else self.e,
)
self.front.append((x, val))
def pop(self):
if not self.front:
while self.back:
_, val = self.back.pop()
self.appendleft(val)
return self.front.pop()[1]
def main():
N = int(input())
X = list(map(int, input().split()))
A = list(map(int, input().split()))
M = max(A) + 1
DP = [[INF] * M for _ in range(3)]
EP = [[INF] * M for _ in range(3)]
for j in range(3):
DP[j][A[0] * 2 - 2 >> 1] = 0
for i in range(1, N):
w = X[i] - X[i - 1]
for j in range(3):
for k in range(M):
DP[j][k] += (k * 2 + 2 - j) * w
EP[j][k] = INF
for j in range(3):
for nj in range(j, 3):
que = QueueAggregation(INF, min)
L, R = 0, 0
for nk in range(M):
nL = max(nk - A[i], A[i] - nk - 2 + j, int(j == 2))
nR = min(M, nk + A[i] + 1 - nj + j)
while L > nL:
L -= 1
que.appendleft(DP[j][L])
while R < nR:
que.append(DP[j][R])
R += 1
while L < nL:
que.pop()
L += 1
EP[nj][nk] = min(EP[nj][nk], que.fold_all())
DP, EP = EP, DP
ANS = DP[2][0]
if ANS >= INF:
ANS = -1
print(ANS)
if __name__ == "__main__":
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0