結果

問題 No.1095 Smallest Kadomatsu Subsequence
コンテスト
ユーザー ああ
提出日時 2026-05-28 20:40:49
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 571 ms / 2,000 ms
コード長 973 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 130 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 162,560 KB
最終ジャッジ日時 2026-05-28 20:41:02
合計ジャッジ時間 8,636 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

def aa(seg,m):
    while m>1:
        m//=2;seg[m]=min(seg[m*2],seg[m*2+1])

def bb(seg,l,r):
    res=1<<60
    while l<r:
        if l&1:
            res=min(seg[l],res);l+=1
        if r&1:
            r-=1;res=min(seg[r],res)
        l//=2;r//=2
    return res

ans=1<<60;n=int(input())
a=list(map(int,input().split()))
s=set(a)
x={};y={};p=0
for i in sorted(list(s)):
    x[i]=p;p+=1
hq1=[]
v=1<<n.bit_length()
seg1=[1<<60]*v*2;seg1[x[a[0]]+v]=a[0];aa(seg1,x[a[0]]+v)
seg2=[1<<60]*v*2
for i in range(1,n):
    seg2[x[a[i]]+v]=a[i];aa(seg2,x[a[i]]+v)
    heapq.heappush(hq1,(a[i],i))
c=a[0];d=a[0]
for i in range(1,n-1):
    if hq1[0][1]==i:
        heapq.heappop(hq1)
    if a[i]>c and a[i]>hq1[0][0]:
        ans=min(ans,a[i]+c+hq1[0][0])
    ans=min(ans,a[i]+bb(seg1,x[a[i]]+1+v,v*2)+bb(seg2,x[a[i]]+1+v,v*2))
    seg2[x[a[i]]+v]=1<<60;aa(seg2,x[a[i]]+v)
    seg1[x[a[i]]+v]=a[i];aa(seg1,x[a[i]]+v)
    c=min(c,a[i])
if ans==1<<60:
    ans=-1
print(ans)
0