結果

問題 No.1767 BLUE to RED
ユーザー gew1fw
提出日時 2025-06-12 14:48:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 329 ms / 2,000 ms
コード長 1,563 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 133,600 KB
最終ジャッジ日時 2025-06-12 14:51:20
合計ジャッジ時間 6,684 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort()

from collections import defaultdict

gaps = defaultdict(list)

for b in B:
    if b < A[0]:
        gaps['before'].append(b)
    elif b > A[-1]:
        gaps['after'].append(b)
    else:
        idx = bisect.bisect_left(A, b) - 1
        gaps[idx].append(b)

total = 0

if 'before' in gaps:
    max_dist = A[0] - min(gaps['before'])
    total += max_dist

if 'after' in gaps:
    max_b = max(gaps['after'])
    max_dist = max_b - A[-1]
    total += max_dist

for j in gaps:
    if j == 'before' or j == 'after':
        continue
    A_j = A[j]
    A_j1 = A[j + 1]
    b_list = gaps[j]
    if not b_list:
        continue
    n_b = len(b_list)
    prefix_max = [0] * n_b
    current_max = 0
    for i in range(n_b):
        current_max = max(current_max, b_list[i] - A_j)
        prefix_max[i] = current_max
    suffix_max = [0] * n_b
    current_max = 0
    for i in range(n_b - 1, -1, -1):
        current_max = max(current_max, A_j1 - b_list[i])
        suffix_max[i] = current_max
    min_steps = float('inf')
    for split in range(n_b + 1):
        if split == 0:
            x = 0
            y = suffix_max[0] if n_b > 0 else 0
        elif split == n_b:
            x = prefix_max[-1]
            y = 0
        else:
            x = prefix_max[split - 1]
            y = suffix_max[split]
        total_steps = x + y
        if total_steps < min_steps:
            min_steps = total_steps
    total += min_steps

print(total)
0