結果

問題 No.107 モンスター
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:31:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,283 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 274,268 KB
最終ジャッジ日時 2025-03-20 20:32:56
合計ジャッジ時間 7,205 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    D = list(map(int, sys.stdin.readline().split()))
    
    bads = []
    goods = []
    for d in D:
        if d < 0:
            bads.append(-d)
        else:
            goods.append(d)
    
    B = len(bads)
    G = len(goods)
    
    memo = {}
    
    # Initial state: bad_mask is all bads remaining, goods_mask is all goods remaining, health=100
    # The mask for bads is bits for bads (assuming first B is bads)
    # Similarly for goods_mask.
    # But for code, since the masks are subsets of the original lists, we need to track each.
    
    bad_all_mask = (1 << B) - 1 if B else 0
    goods_all_mask = (1 << G) - 1 if G else 0
    
    max_health = 0
    
    # We use BFS to explore states in order of their health
    # Initial state: bad_mask=all, goods_mask=all, health=100, max_health=100
    queue = deque()
    queue.append((bad_all_mask, goods_all_mask, 100))
    memo[(bad_all_mask, goods_all_mask, 100)] = 100
    
    while queue:
        bad_mask, goods_mask, h = queue.popleft()
        
        current_level = B - bin(bad_mask).count('1')
        current_max = 100 * (current_level + 1)
        
        # Process possible actions: fight any remaining bad, or use any remaining good
        # Fight a bad monster
        for i in range(B):
            if (bad_mask >> i) & 1:
                damage = bads[i]
                new_h = h - damage
                if new_h <= 0:
                    continue  # invalid
                new_bad_mask = bad_mask ^ (1 << i)
                new_level = current_level + 1
                new_max_after = 100 * (new_level + 1)
                
                # After fighting, you can optionally use some goods
                # Compute delta to max possible healing
                delta = new_max_after - new_h
                if delta < 0:
                    delta = 0
                
                best_heal = 0
                best_goods_mask = goods_mask
                # Precompute all possible subsets of goods_mask and their sums
                # Simplification: greedily pick the largest possible heals
                sorted_goods = sorted([goods[j] for j in range(G) if (goods_mask >> j) & 1], reverse=True)
                temp_sum = 0
                remaining_goods = []
                used_mask = 0
                for g in sorted_goods:
                    if temp_sum + g <= delta:
                        temp_sum += g
                        # Mark the used good
                        idx = goods.index(g)
                        # Check if the index is valid and hasn't been used
                        while (used_mask & (1 << idx)) or (not (goods_mask & (1 << idx))):
                            idx += 1
                        used_mask |= (1 << idx)
                    else:
                        remaining_goods.append(g)
                # Create the new goods mask after using the selected goods
                new_goods_mask = goods_mask ^ used_mask
                new_h_after_heal = new_h + temp_sum
                new_h_after_heal = min(new_h_after_heal, new_max_after)
                
                key = (new_bad_mask, new_goods_mask, new_h_after_heal)
                if key not in memo or new_h_after_heal > memo.get(key, 0):
                    memo[key] = new_h_after_heal
                    queue.append(key)
                    if new_bad_mask == 0:
                        if new_h_after_heal > max_health:
                            max_health = new_h_after_heal
        
        # Use a good monster
        for i in range(G):
            if (goods_mask >> i) & 1:
                heal = goods[i]
                new_goods_mask = goods_mask ^ (1 << i)
                new_h = min(h + heal, current_max)
                key = (bad_mask, new_goods_mask, new_h)
                if key not in memo or new_h > memo.get(key, 0):
                    memo[key] = new_h
                    queue.append(key)
                    if bad_mask == 0 and new_h > max_health:
                        max_health = new_h
    
    # After processing all states, check if all bads are defeated
    print(max_health if max_health > 0 else 0)

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