結果

問題 No.1736 Princess vs. Dragoness
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:54:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,450 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 76,992 KB
最終ジャッジ日時 2025-03-26 15:54:54
合計ジャッジ時間 5,240 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    A = int(input[idx]); idx +=1
    B = int(input[idx]); idx +=1
    X = int(input[idx]); idx +=1
    Y = int(input[idx]); idx +=1
    H = list(map(int, input[idx:idx+N]))
    idx +=N

    sum_H = sum(H)
    max_reduce = [0]*(A+1)  # max_reduce[a] is the maximum reduction possible using 'a' As
    for a in range(1, A+1):
        max_reduce[a] = -1

    for i in range(N):
        hi = H[i]
        if hi ==0:
            continue
        # Determine possible As for this monster
        if hi < X:
            # Can use 0 or 1 As
            for a in range(A, -1, -1):
                if max_reduce[a] != -1:
                    if a +1 <=A and (max_reduce[a+1] < max_reduce[a] + hi):
                        max_reduce[a+1] = max_reduce[a] + hi
        else:
            # Can use k As, where k can be up to hi//X
            max_k = hi // X
            # For large max_k, use binary optimization
            k = 1
            remaining = max_k
            while remaining >0:
                curr_k = min(k, remaining)
                curr_weight = curr_k
                curr_value = curr_k * X
                # Apply this to the DP
                for a in range(A, -1, -1):
                    if max_reduce[a] != -1:
                        if a + curr_weight <=A and (max_reduce[a + curr_weight] < max_reduce[a] + curr_value):
                            max_reduce[a + curr_weight] = max_reduce[a] + curr_value
                remaining -= curr_k
                k *=2
            # Now, consider that using more than max_k As can contribute up to hi
            # So, after using max_k As, the reduction is hi, any additional As contribute nothing
            # So, we can also consider a single item with weight max_k and value hi
            # But to model this, we can check if using max_k+1 As can give hi, but since hi is fixed, it's better to handle it as a separate 0/1 item
            # So, treat it as an item that gives hi reduction with weight any >= max_k, but this is complicated
            # Alternative: after processing the bounded part, handle the case where reduction is hi
            for a in range(A, -1, -1):
                if max_reduce[a] != -1:
                    if a + max_k <=A:
                        possible_reduction = max_reduce[a] + max_k *X
                        if possible_reduction >= hi:
                            possible_reduction = hi
                        if possible_reduction > max_reduce[a + max_k]:
                            max_reduce[a + max_k] = possible_reduction
                    # Now, if we use more than max_k As, the reduction is still hi
                    # So for a >= max_k, we can take the max between current and max_reduce[a -k] + hi for any k >=max_k
                    # This is too complex, but perhaps after the bounded part, we can allow any a >=max_k to have max_reduce[a] = max( max_reduce[a], hi )
                    # However, this is not straightforward

    # Compute the best possible reduction
    best_reduction = 0
    for a in range(A+1):
        if max_reduce[a] > best_reduction:
            best_reduction = max_reduce[a]
    required_B = (sum_H - best_reduction + Y -1) // Y if (sum_H - best_reduction) >0 else 0
    if required_B <= B:
        print("Yes")
    else:
        print("No")

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