結果

問題 No.2157 崖
コンテスト
ユーザー norioc
提出日時 2025-05-30 01:24:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,598 ms / 6,000 ms
コード長 751 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 597 ms
コンパイル使用メモリ 81,892 KB
実行使用メモリ 101,292 KB
最終ジャッジ日時 2025-05-30 01:24:34
合計ジャッジ時間 26,490 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 1 << 60
N, M = map(int, input().split())
D = []
for _ in range(N):
    D.append(sorted(map(int, input().split())))


# 距離 d 以下にできるか
def can(m):
    xs = [True] * M
    for i in range(1, N):
        ys = [False] * M
        p = 0
        for j in range(M):
            if xs[j] == 0: continue
            a = D[i-1][j]

            while p < M and D[i][p] < a:
                p += 1
            while p < M and a <= D[i][p] <= a+m:
                ys[p] = True
                p += 1

        xs = ys

    return any(xs)


lo = 0
hi = INF
ans = hi
while lo <= hi:
    m = (lo + hi) // 2
    if can(m):
        ans = min(ans, m)
        hi = m - 1
    else:
        lo = m + 1

if ans == INF:
    print(-1)
else:
    print(ans)
0