結果

問題 No.2434 RAKUTAN de RAKUTAN
ユーザー gew1fw
提出日時 2025-06-12 19:06:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,594 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 80,720 KB
最終ジャッジ日時 2025-06-12 19:07:01
合計ジャッジ時間 6,672 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    H = int(input[ptr]); ptr +=1
    X = int(input[ptr]); ptr +=1
    
    G = int(input[ptr]); ptr +=1
    g_list = []
    for _ in range(G):
        g_list.append(int(input[ptr]))
        ptr +=1
    g_list.sort()
    
    B = int(input[ptr]); ptr +=1
    b_list = []
    for _ in range(B):
        b_list.append(int(input[ptr]))
        ptr +=1
    b_list.sort()
    
    base_sum = G - B
    
    intervals = set()
    
    for pos in g_list + b_list:
        lower_s = max(0, pos - (X-1))
        upper_s = min(pos-1, N - X)
        if lower_s > upper_s:
            continue
        for s in range(lower_s, upper_s +1):
            start = s + 1
            end = s + X -1
            if end > N -1:
                continue
            intervals.add( (start, end) )
    
    candidates = []
    for start, end in intervals:
        g_left = bisect.bisect_left(g_list, start)
        g_right = bisect.bisect_right(g_list, end)
        g_count = g_right - g_left
        
        b_left = bisect.bisect_left(b_list, start)
        b_right = bisect.bisect_right(b_list, end)
        b_count = b_right - b_left
        
        value = b_count - g_count
        if value > 0:
            candidates.append( (start, end, value) )
    
    candidates.sort(key=lambda x: x[1])
    h_max = min(H, len(candidates))
    
    if not candidates or h_max ==0:
        print(base_sum)
        return
    
    end_times = [c[1] for c in candidates]
    dp = [-float('inf')] * (h_max +1)
    dp[0] = 0
    
    for i in range(len(candidates)):
        start, end, value = candidates[i]
        left = 0
        right = i -1
        best_j = -1
        while left <= right:
            mid = (left + right) //2
            if end_times[mid] < start:
                best_j = mid
                left = mid +1
            else:
                right = mid -1
        
        new_dp = dp.copy()
        for h in range(h_max, 0, -1):
            if best_j == -1:
                if h ==1:
                    new_dp[h] = max(new_dp[h], value)
            else:
                if h-1 >=0 and dp[h-1] != -float('inf'):
                    new_sum = dp[h-1] + value
                    if new_sum > new_dp[h]:
                        new_dp[h] = new_sum
        dp = new_dp
    
    max_sum = max(dp[1:h_max+1]) if h_max >=1 else 0
    if max_sum == -float('inf'):
        max_sum =0
    final_answer = base_sum + max_sum
    print(final_answer)

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