結果

問題 No.2157 崖
ユーザー lam6er
提出日時 2025-03-20 20:23:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,788 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 218,336 KB
最終ジャッジ日時 2025-03-20 20:25:51
合計ジャッジ時間 11,767 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, M = map(int, input[idx:idx+2])
    idx += 2
    D = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+M]))
        idx += M
        D.append(sorted(row))  # Pre-sort each difficulty tier

    # Check if any solution exists at all by checking with a very large d
    def is_possible(d):
        possible_prev = D[0].copy()
        possible_prev.sort()
        for i in range(1, N):
            current_D = D[i]
            current_possible = []
            possible_prev_sorted = possible_prev
            for y in current_D:
                # Find if there exists x_prev in possible_prev such that x_prev <= y and y - x_prev <= d
                low = y - d
                # Find the first x >= low in possible_prev
                left_idx = bisect.bisect_left(possible_prev_sorted, low)
                if left_idx < len(possible_prev_sorted) and possible_prev_sorted[left_idx] <= y:
                    current_possible.append(y)
            if not current_possible:
                return False
            # Use a set to avoid duplicates and sort to maintain order
            current_possible = sorted(list(set(current_possible)))
            possible_prev = current_possible
        return True

    # Check if even the maximum possible d can't form a sequence
    if not is_possible(10**18):
        print(-1)
        return

    # Binary search for the minimum possible d
    left = 0
    right = 10**18
    answer = 10**18
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    print(answer)

if __name__ == '__main__':
    main()
0