結果

問題 No.2434 RAKUTAN de RAKUTAN
ユーザー gew1fw
提出日時 2025-06-12 21:04:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,748 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 80,764 KB
最終ジャッジ日時 2025-06-12 21:06:02
合計ジャッジ時間 6,019 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 4 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx +=1
    H = int(data[idx]); idx +=1
    X = int(data[idx]); idx +=1
    
    G = int(data[idx]); idx +=1
    gain = list(map(int, data[idx:idx+G]))
    idx += G
    
    B = int(data[idx]); idx +=1
    lose = list(map(int, data[idx:idx+B]))
    idx += B
    
    # Collect all important positions
    P = set()
    P.add(0)
    P.add(N)
    for g in gain:
        P.add(g)
    for l in lose:
        P.add(l)
    P = sorted(list(P))
    
    # Create a dictionary to check if a position is gain, lose, or neither
    pos_info = {}
    gain_set = set(gain)
    lose_set = set(lose)
    for p in P:
        if p in gain_set:
            pos_info[p] = 1
        elif p in lose_set:
            pos_info[p] = -1
        else:
            pos_info[p] = 0
    
    # Precompute next_normal and next_leap for each p in P
    next_normal = {}
    next_leap = {}
    for i in range(len(P)):
        p = P[i]
        # next_normal is the next p in P, if exists
        if i +1 < len(P):
            next_normal[p] = P[i+1]
        else:
            next_normal[p] = None
        
        # next_leap: p + X
        p_leap = p + X
        if p_leap > N:
            next_leap[p] = None
            continue
        
        # find the first position in P >= p_leap
        low = i
        high = len(P) -1
        res = None
        while low <= high:
            mid = (low + high) // 2
            if P[mid] >= p_leap:
                res = P[mid]
                high = mid -1
            else:
                low = mid +1
        if res is not None:
            next_leap[p] = res
        else:
            next_leap[p] = None
    
    # Use a priority queue and a dictionary to track max units
    heap = []
    max_units = {}
    
    # Initial state: p=0, h=H, u=0
    initial_u = 0
    initial_p = 0
    initial_h = H
    heapq.heappush(heap, (-initial_u, initial_p, initial_h))
    max_units[(initial_p, initial_h)] = initial_u
    
    answer = -float('inf')
    
    while heap:
        current_u_neg, current_p, current_h = heapq.heappop(heap)
        current_u = -current_u_neg
        
        # Skip if a better state already exists
        if (current_p, current_h) in max_units and max_units[(current_p, current_h)] > current_u:
            continue
        
        # Update the answer if current_p is N
        if current_p == N:
            answer = max(answer, current_u)
            continue
        
        # Process normal move
        q = next_normal.get(current_p, None)
        if q is not None:
            delta_u = pos_info.get(q, 0)
            new_u = current_u + delta_u
            new_h = current_h
            new_p = q
            key = (new_p, new_h)
            if key not in max_units or new_u > max_units[key]:
                max_units[key] = new_u
                heapq.heappush(heap, (-new_u, new_p, new_h))
        
        # Process leap move
        if current_h > 0:
            r = next_leap.get(current_p, None)
            if r is not None:
                delta_u = pos_info.get(r, 0)
                new_u = current_u + delta_u
                new_h = current_h - 1
                new_p = r
                key = (new_p, new_h)
                if key not in max_units or new_u > max_units[key]:
                    max_units[key] = new_u
                    heapq.heappush(heap, (-new_u, new_p, new_h))
    
    # Determine the maximum u when reaching N
    max_u = -float('inf')
    for (p, h), u in max_units.items():
        if p == N and u > max_u:
            max_u = u
    
    print(max_u if max_u != -float('inf') else 0)

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