#1059600 (PyPy3) No.1736 Princess vs. Dragoness

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX