結果

問題 No.1767 BLUE to RED
ユーザー qwewe
提出日時 2025-05-14 13:22:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 2,683 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 82,684 KB
実行使用メモリ 130,372 KB
最終ジャッジ日時 2025-05-14 13:24:51
合計ジャッジ時間 5,215 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    total_ops = 0
    b_ptr = 0 # Current position in B array, points to the next B cell to consider

    # Case 1: Blue cells before A[0]
    if N > 0:
        first_A = A[0]
        min_B_val_before_first_A = float('inf')
        has_any_B_before_first_A = False
        
        temp_scan_ptr = 0 
        while temp_scan_ptr < M and B[temp_scan_ptr] < first_A:
            min_B_val_before_first_A = min(min_B_val_before_first_A, B[temp_scan_ptr])
            has_any_B_before_first_A = True
            temp_scan_ptr += 1
        
        if has_any_B_before_first_A:
            total_ops += (first_A - min_B_val_before_first_A)
        b_ptr = temp_scan_ptr

    # Case 2: Blue cells between A[i] and A[i+1]
    for i in range(N - 1): 
        A_L = A[i]
        A_R = A[i+1]

        gap_blues = []
        
        temp_scan_ptr = b_ptr 
        while temp_scan_ptr < M and B[temp_scan_ptr] < A_R:
            # B[temp_scan_ptr] > A_L must hold due to sorted distinct A, B and b_ptr logic
            gap_blues.append(B[temp_scan_ptr])
            temp_scan_ptr += 1
        
        if not gap_blues:
            b_ptr = temp_scan_ptr 
            continue

        p = len(gap_blues)
        cost_for_gap = A_R - A_L 

        for k_count_from_left in range(p + 1): 
            ops_L_path = 0
            if k_count_from_left > 0: 
                # покрыть первые k_count_from_left синих ячеек (индексы 0 до k_count_from_left-1) от A_L
                ops_L_path = gap_blues[k_count_from_left-1] - A_L
            
            ops_R_path = 0
            if k_count_from_left < p: 
                # покрыть оставшиеся синие ячейки (индексы k_count_from_left до p-1) от A_R
                ops_R_path = A_R - gap_blues[k_count_from_left]
            
            cost_for_gap = min(cost_for_gap, ops_L_path + ops_R_path)
        
        total_ops += cost_for_gap
        b_ptr = temp_scan_ptr 

    # Case 3: Blue cells after A[N-1]
    if N > 0:
        last_A = A[N-1]
        max_B_val_after_last_A = float('-inf')
        has_any_B_after_last_A = False

        temp_scan_ptr = b_ptr
        while temp_scan_ptr < M: 
            max_B_val_after_last_A = max(max_B_val_after_last_A, B[temp_scan_ptr])
            has_any_B_after_last_A = True
            temp_scan_ptr += 1
            
        if has_any_B_after_last_A:
            total_ops += (max_B_val_after_last_A - last_A)

    print(total_ops)

solve()
0