結果
問題 |
No.1095 Smallest Kadomatsu Subsequence
|
ユーザー |
|
提出日時 | 2020-06-27 17:33:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 540 ms / 2,000 ms |
コード長 | 1,261 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 110,464 KB |
最終ジャッジ日時 | 2024-07-05 18:04:01 |
合計ジャッジ時間 | 7,227 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
class BinaryIndexedTree: def __init__(self,n,default = 10**9): self.s = [default]*(n+1) self.n = n # idxは0-indexted def reset(self,val,idx): idx += 1 while idx < self.n+1: self.s[idx] = min(self.s[idx], val) idx += idx&(-idx) return def get(self,idx): idx += 1 res = 10**9 while idx > 0: res = min(res, self.s[idx]) idx -= idx&(-idx) return res n = int(input()) A = list(map(int, input().split())) mod = 10**9 + 7 Rm = [[0]*n,[0]*n] B = sorted(range(n),key = lambda x:A[x]) ans = 10**9 for b in B: left = Rm[0][b] right = Rm[1][b] if left*right > 0: ans = min(ans, left + right + A[b]) idx = b while idx < n: if Rm[0][idx] != 0:break Rm[0][idx] = A[b] idx += 1 idx = b while idx >= 0: if Rm[1][idx] != 0:break Rm[1][idx] = A[b] idx -= 1 RM = [BinaryIndexedTree(n), BinaryIndexedTree(n)] for b in B[::-1]: left = RM[0].get(b) right = RM[1].get(n-b-1) if (10**9-left)*(10**9-right) > 0: ans = min(ans, left + right + A[b]) RM[0].reset(A[b], b) RM[1].reset(A[b], n-b-1) print(ans if ans != 10**9 else -1)