結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
![]() |
提出日時 | 2020-04-02 22:08:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 700 ms / 1,500 ms |
コード長 | 1,731 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 184,856 KB |
最終ジャッジ日時 | 2024-06-28 15:20:36 |
合計ジャッジ時間 | 19,174 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from bisect import bisect_left class SegTree: """ segment tree with point modification and range product access. """ data_unit = 1 << 30 data_f = min def __init__(self, N): self.N = N self.data = [self.data_unit] * (N + N) def build(self, raw_data): data = self.data f = self.data_f N = self.N data[N:] = raw_data[:] for i in range(N - 1, 0, -1): data[i] = f(data[i << 1], data[i << 1 | 1]) def set_val(self, i, x): data = self.data f = self.data_f i += self.N data[i] = x while i > 1: data[i >> 1] = f(data[i], data[i ^ 1]) i >>= 1 def fold(self, L, R): """ compute for [L, R) """ vL = vR = self.data_unit data = self.data f = self.data_f L += self.N R += self.N while L < R: if L & 1: vL = f(vL, data[L]) L += 1 if R & 1: R -= 1 vR = f(data[R], vR) L >>= 1 R >>= 1 return f(vL, vR) N = int(readline()) A = (0,) + tuple(map(int, readline().split())) X = (0,) + tuple(map(int, readline().split())) Y = (0,) + tuple(map(int, readline().split())) dp = [0] * (N + 1) dp1 = SegTree(N + 1) dp2 = SegTree(N + 1) for i in range(1, N + 1): dp1.set_val(i, dp[i - 1] - X[i] + Y[i]) dp2.set_val(i, dp[i - 1] + X[i] + Y[i]) n = bisect_left(X, A[i], lo=0, hi=i + 1) dp[i] = min(A[i] + dp1.fold(0, n), -A[i] + dp2.fold(n, i + 1)) print(dp[-1])