結果

問題 No.1715 Dinner 2
コンテスト
ユーザー titia
提出日時 2026-02-01 05:12:54
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,249 ms / 2,000 ms
コード長 861 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 311 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 78,848 KB
最終ジャッジ日時 2026-02-01 05:13:08
合計ジャッジ時間 14,049 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

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

OK=-10**8
NG=1

while OK<NG-1:
    mid=(OK+NG)//2

    DP=[0]*N
    LEFT=[0]*N
    RIGHT=[0]*N

    for day in range(D):
        NDP=[-1<<60]*N

        for i in range(N):
            if i+1<N and LEFT[i+1]-P[i][0]>=mid:
                NDP[i]=max(NDP[i],LEFT[i+1]-P[i][0]+P[i][1])
            if i-1>=0 and RIGHT[i-1]-P[i][0]>=mid:
                NDP[i]=max(NDP[i],RIGHT[i-1]-P[i][0]+P[i][1])

        DP=NDP

        LEFT=[-1<<60]*N
        RIGHT=[-1<<60]*N

        LEFT[-1]=DP[-1]
        for i in range(N-2,-1,-1):
            LEFT[i]=max(LEFT[i+1],DP[i])
        RIGHT[0]=DP[0]
        for i in range(1,N):
            RIGHT[i]=max(RIGHT[i-1],DP[i])

    if max(DP)<=-1<<60:
        NG=mid
    else:
        OK=mid

print(OK)
0