結果

問題 No.2434 RAKUTAN de RAKUTAN
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:29:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,546 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 81,124 KB
最終ジャッジ日時 2025-04-16 16:30:18
合計ジャッジ時間 6,290 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 17 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    H = int(input[idx]); idx +=1
    X = int(input[idx]); idx +=1
    
    G = int(input[idx]); idx +=1
    g_list = list(map(int, input[idx:idx+G]))
    idx += G
    g_list.sort()
    
    B = int(input[idx]); idx +=1
    b_list = list(map(int, input[idx:idx+B]))
    idx += B
    b_list.sort()
    
    intervals = set()
    for x in g_list + b_list:
        start_a = max(0, x - (X-1))
        end_a = x - 1
        for a in range(start_a, end_a + 1):
            s = a + 1
            e = a + X - 1
            if e > N:
                continue
            intervals.add((s, e))
    
    filtered_intervals = []
    for s, e in intervals:
        left_g = bisect.bisect_left(g_list, s)
        right_g = bisect.bisect_right(g_list, e)
        count_g = right_g - left_g
        
        left_b = bisect.bisect_left(b_list, s)
        right_b = bisect.bisect_right(b_list, e)
        count_b = right_b - left_b
        
        value = count_b - count_g
        if value > 0:
            filtered_intervals.append((s, e, value))
    
    filtered_intervals.sort(key=lambda x: x[1])
    
    latest = [-1] * len(filtered_intervals)
    for i in range(len(filtered_intervals)):
        s_i = filtered_intervals[i][0]
        low, high = 0, i - 1
        best_j = -1
        while low <= high:
            mid = (low + high) // 2
            if filtered_intervals[mid][1] < s_i:
                best_j = mid
                low = mid + 1
            else:
                high = mid - 1
        latest[i] = best_j
    
    max_possible_k = min(H, len(filtered_intervals))
    dp = [-float('inf')] * (max_possible_k + 1)
    dp[0] = 0
    
    for i in range(len(filtered_intervals)):
        s, e, value = filtered_intervals[i]
        j = latest[i]
        new_dp = dp.copy()
        for k in range(1, max_possible_k + 1):
            if j == -1:
                if k == 1:
                    new_dp[k] = max(new_dp[k], value)
            else:
                if k - 1 >= 0 and dp[k - 1] != -float('inf'):
                    possible = dp[k - 1] + value
                    if possible > new_dp[k]:
                        new_dp[k] = possible
        if value > new_dp[1]:
            new_dp[1] = value
        dp = new_dp
    
    max_sum = max(dp) if max(dp) != -float('inf') else 0
    total_g = G
    total_b = B
    result = (total_g - total_b) + max_sum
    print(result)

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