結果
問題 | No.2006 Decrease All to Zero |
ユーザー |
|
提出日時 | 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 |
ソースコード
import sysinput = sys.stdin.buffer.readlineINF = 10 ** 18class QueueAggregation:def __init__(self, e, f):self.e = eself.f = fself.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) + 1DP = [[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] = 0for 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) * wEP[j][k] = INFfor j in range(3):for nj in range(j, 3):que = QueueAggregation(INF, min)L, R = 0, 0for 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 -= 1que.appendleft(DP[j][L])while R < nR:que.append(DP[j][R])R += 1while L < nL:que.pop()L += 1EP[nj][nk] = min(EP[nj][nk], que.fold_all())DP, EP = EP, DPANS = DP[2][0]if ANS >= INF:ANS = -1print(ANS)if __name__ == "__main__":main()