結果

問題 No.1015 おつりは要らないです
ユーザー gew1fw
提出日時 2025-06-12 20:57:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,135 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 81,680 KB
実行使用メモリ 102,580 KB
最終ジャッジ日時 2025-06-12 21:01:31
合計ジャッジ時間 4,598 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    t_list = []
    for a in A:
        t = (a // 1000) + 1
        t_list.append(t)
    
    t_list.sort(reverse=True)

    for t in t_list:
        # Try to allocate as much as possible with 10000
        c = min(t // 10, Z)
        rem = t - c * 10

        # Try to allocate as much as possible with 5000
        b = min(rem // 5, Y)
        rem -= b * 5

        a = rem

        if a <= X:
            X -= a
            Y -= b
            Z -= c
            continue
        else:
            # Check if we can increase b to cover the remaining a
            min_b = (rem + 4) // 5
            if min_b <= Y:
                # Allocate b as min_b
                b = min_b
                rem = t - c * 10 - 5 * b
                a = max(rem, 0)
                if a <= X:
                    X -= a
                    Y -= b
                    Z -= c
                    continue
            # If not, try to increase c
            if c < Z:
                c_new = c + 1
                rem_new = t - c_new * 10
                if rem_new < 0:
                    rem_new = 0
                b_new = min(rem_new // 5, Y)
                rem_new -= b_new * 5
                a_new = rem_new
                if a_new <= X:
                    if c_new <= Z:
                        X -= a_new
                        Y -= b_new
                        Z -= c_new
                        continue
            # If none of the above works, try to use higher c and b to make a=0
            # Calculate the minimal b needed to cover rem
            min_b_needed = (rem + 4) // 5
            if min_b_needed <= Y:
                b = min_b_needed
                rem = t - c * 10 - 5 * b
                a = max(rem, 0)
                if a <= X:
                    X -= a
                    Y -= b
                    Z -= c
                    continue
            # If still not possible, check if we can increase c beyond initial c
            max_possible_c = min(t // 10 + 1, Z)
            found = False
            for c_candidate in range(c, max_possible_c + 1):
                rem_candidate = t - c_candidate * 10
                if rem_candidate < 0:
                    rem_candidate = 0
                min_b_candidate = (rem_candidate + 4) // 5
                if min_b_candidate <= Y:
                    b_candidate = min_b_candidate
                    a_candidate = max(rem_candidate - 5 * b_candidate, 0)
                    if a_candidate <= X:
                        X -= a_candidate
                        Y -= b_candidate
                        Z -= c_candidate
                        found = True
                        break
            if found:
                continue
            # If all else fails, output No
            print("No")
            return
    
    print("Yes")

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