提出 #65028669

ソースコード 拡げる

N,X = list(map(int,input().split()))
kitai = []
for _ in range(N):
    s,c,p = list(map(int,input().split()))
    kitai.append((s*p / 100 ,5000-c,s,p))

kitai.sort(reverse=True)

from decimal import Decimal, getcontext
getcontext().prec = 15  # 精度を高く

queue = []
# que = (p,sum(s),x,[done])
queue.append((Decimal(1),0,0,[]))
ans = 0
while queue:
    pn,sums,x,done = queue.pop(0)
    appended = False
    for i in range(N):
        if i in done:continue
        kitaichi,c,s,p = kitai[i]
        c = 5000 - c
        if x + c <= X:
            queue.append((pn*Decimal(p)/100 , sums+s , x+c , done + [i]))
            queue.append((pn*Decimal(100-p)/100 , sums , x+c , done))
            appended = True
            break
    if appended : continue
    ans += pn * sums
    
print(ans)

提出情報

提出日時
問題 E - Payment Required
ユーザ tamagonist
言語 Python (PyPy 3.10-v7.3.12)
得点 0
コード長 825 Byte
結果 WA
実行時間 2215 ms
メモリ 154756 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 450
結果
AC × 3
TLE × 1
AC × 21
WA × 4
TLE × 18
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 02_random_30.txt, 02_random_31.txt, 02_random_32.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 222 ms 87808 KiB
00_sample_01.txt AC 149 ms 87904 KiB
00_sample_02.txt AC 150 ms 88040 KiB
00_sample_03.txt TLE 2213 ms 119012 KiB
01_handmade_00.txt AC 149 ms 87996 KiB
01_handmade_01.txt AC 146 ms 88016 KiB
01_handmade_02.txt AC 314 ms 95536 KiB
01_handmade_03.txt AC 229 ms 93208 KiB
01_handmade_04.txt TLE 2213 ms 115228 KiB
01_handmade_05.txt TLE 2213 ms 121952 KiB
02_random_00.txt WA 147 ms 88136 KiB
02_random_01.txt AC 146 ms 87916 KiB
02_random_02.txt WA 157 ms 88748 KiB
02_random_03.txt AC 148 ms 87876 KiB
02_random_04.txt AC 146 ms 88044 KiB
02_random_05.txt TLE 2213 ms 130700 KiB
02_random_06.txt TLE 2214 ms 145148 KiB
02_random_07.txt TLE 2215 ms 149764 KiB
02_random_08.txt TLE 2213 ms 125880 KiB
02_random_09.txt AC 142 ms 88060 KiB
02_random_10.txt AC 144 ms 87900 KiB
02_random_11.txt AC 304 ms 99476 KiB
02_random_12.txt TLE 2213 ms 115020 KiB
02_random_13.txt AC 144 ms 87776 KiB
02_random_14.txt AC 141 ms 87908 KiB
02_random_15.txt AC 144 ms 87980 KiB
02_random_16.txt AC 145 ms 88032 KiB
02_random_17.txt AC 145 ms 87920 KiB
02_random_18.txt AC 144 ms 88004 KiB
02_random_19.txt TLE 2213 ms 121100 KiB
02_random_20.txt TLE 2213 ms 115084 KiB
02_random_21.txt AC 141 ms 87924 KiB
02_random_22.txt WA 140 ms 87880 KiB
02_random_23.txt AC 159 ms 88772 KiB
02_random_24.txt WA 146 ms 87992 KiB
02_random_25.txt TLE 2215 ms 154756 KiB
02_random_26.txt TLE 2213 ms 120312 KiB
02_random_27.txt TLE 2213 ms 121268 KiB
02_random_28.txt TLE 2213 ms 115036 KiB
02_random_29.txt TLE 2215 ms 148376 KiB
02_random_30.txt TLE 2213 ms 123156 KiB
02_random_31.txt TLE 2214 ms 142748 KiB
02_random_32.txt TLE 2213 ms 123680 KiB