結果

問題 No.1736 Princess vs. Dragoness
ユーザー lam6er
提出日時 2025-04-15 22:57:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,555 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,024 KB
実行使用メモリ 76,216 KB
最終ジャッジ日時 2025-04-15 22:59:10
合計ジャッジ時間 3,351 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import math

def main():
    N, A, B, X, Y = map(int, sys.stdin.readline().split())
    H = list(map(int, sys.stdin.readline().split()))
    
    # Precompute required A's for each monster
    a = [math.ceil(h / X) for h in H]
    prefix_a = [0] * (N + 1)
    for i in range(N):
        prefix_a[i+1] = prefix_a[i] + a[i]
    
    for m in range(N+1):
        required_A = prefix_a[m]
        if required_A > A:
            continue
        
        remaining_H = H[m:]
        if not remaining_H:
            print("Yes")
            return
        
        sum_remaining = sum(remaining_H)
        if sum_remaining == 0:
            print("Yes")
            return
        
        low = 0
        high = (sum_remaining + Y - 1) // Y
        answer_k = None
        
        while low <= high:
            mid = (low + high) // 2
            sum_d = 0
            valid = True
            for h in remaining_H:
                sum_available = mid * Y - sum_d
                if sum_available <= 0:
                    if h > 0:
                        valid = False
                    break
                d = min(h, sum_available)
                sum_d += d
                if d < h:
                    valid = False
                    break
            if valid:
                answer_k = mid
                high = mid - 1
            else:
                low = mid + 1
        
        if answer_k is not None and answer_k <= B:
            print("Yes")
            return
    
    print("No")

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