結果
問題 | No.2332 Make a Sequence |
ユーザー | navel_tos |
提出日時 | 2024-02-25 21:44:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 953 ms / 2,000 ms |
コード長 | 4,212 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 224,684 KB |
最終ジャッジ日時 | 2024-02-25 21:45:06 |
合計ジャッジ時間 | 32,491 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
53,460 KB |
testcase_01 | AC | 35 ms
53,460 KB |
testcase_02 | AC | 36 ms
53,460 KB |
testcase_03 | AC | 36 ms
53,460 KB |
testcase_04 | AC | 36 ms
53,460 KB |
testcase_05 | AC | 36 ms
53,460 KB |
testcase_06 | AC | 38 ms
53,460 KB |
testcase_07 | AC | 345 ms
205,520 KB |
testcase_08 | AC | 106 ms
103,600 KB |
testcase_09 | AC | 230 ms
148,132 KB |
testcase_10 | AC | 275 ms
181,512 KB |
testcase_11 | AC | 206 ms
150,060 KB |
testcase_12 | AC | 344 ms
224,676 KB |
testcase_13 | AC | 362 ms
224,652 KB |
testcase_14 | AC | 336 ms
224,644 KB |
testcase_15 | AC | 336 ms
224,568 KB |
testcase_16 | AC | 334 ms
224,580 KB |
testcase_17 | AC | 356 ms
224,680 KB |
testcase_18 | AC | 336 ms
224,684 KB |
testcase_19 | AC | 332 ms
224,572 KB |
testcase_20 | AC | 343 ms
224,520 KB |
testcase_21 | AC | 337 ms
224,580 KB |
testcase_22 | AC | 353 ms
223,432 KB |
testcase_23 | AC | 353 ms
223,244 KB |
testcase_24 | AC | 354 ms
223,788 KB |
testcase_25 | AC | 352 ms
223,408 KB |
testcase_26 | AC | 348 ms
222,844 KB |
testcase_27 | AC | 379 ms
222,484 KB |
testcase_28 | AC | 377 ms
222,908 KB |
testcase_29 | AC | 379 ms
222,920 KB |
testcase_30 | AC | 381 ms
222,900 KB |
testcase_31 | AC | 379 ms
222,492 KB |
testcase_32 | AC | 389 ms
221,132 KB |
testcase_33 | AC | 393 ms
221,456 KB |
testcase_34 | AC | 393 ms
221,368 KB |
testcase_35 | AC | 396 ms
221,240 KB |
testcase_36 | AC | 389 ms
221,360 KB |
testcase_37 | AC | 402 ms
208,200 KB |
testcase_38 | AC | 408 ms
220,452 KB |
testcase_39 | AC | 421 ms
220,604 KB |
testcase_40 | AC | 405 ms
220,128 KB |
testcase_41 | AC | 401 ms
220,912 KB |
testcase_42 | AC | 570 ms
178,140 KB |
testcase_43 | AC | 560 ms
177,516 KB |
testcase_44 | AC | 498 ms
177,392 KB |
testcase_45 | AC | 501 ms
186,140 KB |
testcase_46 | AC | 535 ms
177,372 KB |
testcase_47 | AC | 932 ms
205,592 KB |
testcase_48 | AC | 926 ms
205,572 KB |
testcase_49 | AC | 940 ms
205,580 KB |
testcase_50 | AC | 953 ms
205,592 KB |
testcase_51 | AC | 927 ms
205,592 KB |
testcase_52 | AC | 385 ms
222,192 KB |
testcase_53 | AC | 382 ms
222,380 KB |
testcase_54 | AC | 383 ms
222,392 KB |
testcase_55 | AC | 382 ms
222,236 KB |
testcase_56 | AC | 384 ms
222,200 KB |
testcase_57 | AC | 348 ms
222,892 KB |
testcase_58 | AC | 334 ms
222,748 KB |
testcase_59 | AC | 343 ms
222,428 KB |
testcase_60 | AC | 346 ms
222,264 KB |
testcase_61 | AC | 335 ms
221,840 KB |
testcase_62 | AC | 836 ms
220,160 KB |
ソースコード
#MMA Contest 015 - K Make a Sequence #リジャッジでTLEになっていたので(は?) リベンジ #static Li Chao Tree class Li_Chao_Tree: def __init__(self, X_list): #X_list: 線分追加・最小値計算で使用する、すべてのx座標 #_X[i] = x, _D[x] = i x座標とLi Chao Tree上のノードを対応 #_L[i] = (a, b): 区間の最大値候補たり得る線分 y = ax + b #_S[i] = (Lt, mid, Rt): ノードの区間(index表記) [X[Lt], X[Rt]]の閉区間が対象 self._inf = inf = 4 * 10 ** 18 X_list = sorted(set(X_list + [inf])) self._N = N = len(X_list) self._logN = logN = (N - 1).bit_length() self._size = size = 1 << logN self._X = X = X_list + [inf] * (size - N) self._D = D = {x: i for i, x in enumerate(X_list)} self._L = L = [None] * 2 * size self._S = S = [None] * size + [(i, i, i) for i in range(size)] for i in range(size - 1, 0, -1): S[i] = (S[i << 1][0], S[i << 1 | 1][0], S[i << 1 | 1][2]) def _f(self, line, x): return line[0] * x + line[1] def _add_line(self, line, i): #ノードi(と、その子)に線分を追加 Q = [(i, line)] while Q: i, line = Q.pop() if self._L[i] == None: self._L[i] = line continue Lt, mid, Rt = self._S[i] xL, xM, xR = self._X[Lt], self._X[mid], self._X[Rt] hL = self._f(line, xL) < self._f(self._L[i], xL) hM = self._f(line, xM) < self._f(self._L[i], xM) hR = self._f(line, xR) < self._f(self._L[i], xR) if hL == hR == True: self._L[i] = line continue if hL == hR == False: continue if hM == True: self._L[i], line = line, self._L[i] if hL != hM: Q.append((i << 1, line)) else: Q.append((i << 1 | 1, line)) def add_line(self, line, x_Lt = None, x_Rt = None): #半開区間[x_Lt, x_Rt)に線分追加 if x_Lt == x_Rt == None: self._add_line(line, 1) return Lt = self._D[x_Lt] if x_Lt != None else 0 Rt = self._D[x_Rt] if x_Rt != None else self._D[self._inf] Lt, Rt = Lt + self._size, Rt + self._size while Lt < Rt: if Lt & 1: self._add_line(line, Lt) Lt += 1 if Rt & 1: Rt -= 1 self._add_line(line, Rt) Lt >>= 1 Rt >>= 1 def fold(self, x): #座標xの最小値を計算 i = self._D[x] + self._size ans = self._inf while i > 0: if self._L[i]: ans = min(ans, self._f(self._L[i], x)) i >>= 1 return ans #Z-algorithm TとS[i:]のLCP判定は、T+'$'+S のようにSに出ない文字を挟んで実行するとよい #Reference: https://tjkendev.github.io/procon-library/python/string/z-algorithm.html def Z_algorithm(S): #SとS[i:]の最長共通接頭辞を求める N=len(S); A=[0]*N; i,j=1,0; A[0]=L=N while i<L: while i+j<L and S[j]==S[i+j]: j+=1 if not j: i+=1; continue A[i]=j; k=1 while L-i>k<j-A[k]: A[i+k]=A[k]; k+=1 i+=k; j-=k return A #入力受取 N, M = map(int, input().split()) A = list(map(int, input().split())) B = list(map(int, input().split())) C = list(map(int, input().split())) #Bの(Aとの)最長共通接頭辞を計算 same = Z_algorithm(A + [0] + B)[N + 1:] #DP[i]: 列Sを[0: i)まで(つまり、i文字目の直前まで)一致させるための最小コスト とする #これはLi Chao Treeの線分追加で計算が可能 #k = same[i]として、[i: i + k)に y = C[i] * x + (DP[i] - C[i] * i) の線分を追加する LCT = Li_Chao_Tree([i for i in range(M + 2)]) LCT.add_line((0, 0), 0, 1) #初期化 for i in range(M): b = LCT.fold(i) k = same[i] if b > 10 ** 18 or k == 0: continue LCT.add_line((C[i], b - C[i] * i), i + 1, min(M, i + k) + 1) #答えを出力 ans = LCT.fold(M) print(ans if ans < 10 ** 18 else -1)