結果

問題 No.2157 崖
ユーザー lam6er
提出日時 2025-03-31 17:43:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,469 ms / 6,000 ms
コード長 2,157 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,744 KB
実行使用メモリ 251,488 KB
最終ジャッジ日時 2025-03-31 17:44:10
合計ジャッジ時間 15,313 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx +=2
    D = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+M]))
        idx += M
        D.append(row)
    
    # Initialize DP for the first row
    current = sorted(D[0])
    unique_current = []
    prev_x = None
    for x in current:
        if x != prev_x:
            unique_current.append(x)
            prev_x = x
    dp_prev = {x: 0 for x in unique_current}
    if not dp_prev:
        print(-1)
        return
    
    k = 5  # Number of neighboring elements to check
    
    for i in range(1, N):
        current_row = D[i]
        current_row_sorted = sorted(current_row)
        # Create unique x candidates in sorted order
        unique_x = []
        prev_x = None
        for x in current_row_sorted:
            if x != prev_x:
                unique_x.append(x)
                prev_x = x
        
        dp_current = {}
        prev_ys = sorted(dp_prev.keys())
        if not prev_ys:
            print(-1)
            return
        
        for x in sorted(unique_x):
            j = bisect.bisect_right(prev_ys, x) - 1
            if j < 0:
                continue  # no valid y
            
            start = max(0, j - k)
            end = min(len(prev_ys)-1, j + k)
            min_max = float('inf')
            
            for yj in range(start, end + 1):
                y = prev_ys[yj]
                if y > x:
                    continue
                current_max = max(dp_prev[y], x - y)
                if current_max < min_max:
                    min_max = current_max
            
            if min_max != float('inf'):
                if x in dp_current:
                    if min_max < dp_current[x]:
                        dp_current[x] = min_max
                else:
                    dp_current[x] = min_max
        
        dp_prev = dp_current
        if not dp_prev:
            print(-1)
            return
    
    if dp_prev:
        print(min(dp_prev.values()))
    else:
        print(-1)

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