結果

問題 No.2157 崖
ユーザー titiatitia
提出日時 2022-12-10 02:39:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,719 ms / 6,000 ms
コード長 2,067 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 106,876 KB
最終ジャッジ日時 2024-10-14 23:28:13
合計ジャッジ時間 17,726 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from bisect import bisect

N,M=map(int,input().split())

seg_el=1<<((M+1).bit_length()) # Segment treeの台の要素数

def getvalue(n,seg_el): # 一点の値を取得
    i=n+seg_el
    ANS=1<<60
    
    ANS=min(SEG[i],ANS)
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS=min(SEG[i],ANS)
        i>>=1

    return ANS

def updates(l,r,x): # 区間[l,r)のminを更新.
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=min(x,SEG[L])
            L+=1

        if R & 1:
            R-=1
            SEG[R]=min(x,SEG[R])
        L>>=1
        R>>=1


D=[list(map(int,input().split())) for i in range(N)]

if N==1:
    print(0)
    exit()

for i in range(N):
    D[i].sort()

DP=[0]*M
for i in range(N-1):
    #print("!",DP)
    SEG=[1<<30]*(2*seg_el)
    NDP2=[-1]*M

    TO=D[i+1]

    for j in range(M):
        if DP[j]==-1:
            continue

        x=D[i][j]

        k=bisect(TO,x-1)
        l=bisect(TO,x+DP[j])

        while k<len(TO) and TO[k]<x:
            k+=1

        while l<len(TO) and TO[l]<=x+DP[j]:
            l+=1

        updates(k,l,DP[j])
        if l<len(TO):
            if NDP2[l]==-1:
                NDP2[l]=D[i+1][l]-x
            else:
                NDP2[l]=min(NDP2[l],D[i+1][l]-x)

    #print([getvalue(xx,seg_el) for xx in range(M)])
    #print(NDP2)

    for j in range(M-1):
        if NDP2[j]==-1:
            continue
        if NDP2[j+1]!=-1:
            NDP2[j+1]=min(NDP2[j+1],NDP2[j]+TO[j+1]-TO[j])
        else:
            NDP2[j+1]=NDP2[j]+TO[j+1]-TO[j]
            

    DP=[0]*M

    for j in range(M):
        x=getvalue(j,seg_el)
        y=NDP2[j]

        if x==1<<30 and y==-1:
            DP[j]=-1
        elif x==1<<30:
            DP[j]=y
        elif y==-1:
            DP[j]=x
        else:
            DP[j]=min(x,y)
        
ANS=1<<60

for i in range(M):
    if DP[i]==-1:
        continue
    else:
        ANS=min(ANS,DP[i])

if ANS==1<<60:
    print(-1)
else:
    print(ANS)
0