提出 #61842706

ソースコード 拡げる

import heapq
def solve():
    N, M = map(int, input().split())
    list_P = list(map(int, input().split()))
    list_P.sort()
    ans = 0
    for p in list_P:
        ans += M / p
    ans = ans ** 0.5
    # print(ans)
    K = M / ans
    kk = [K / p for p in list_P]
    # print(sum(k ** 2 * p for k, p in zip(kk, list_P)))    
    init_sol = [int(k) + 1for k in kk]
    cur_cost = sum(k ** 2 * p for k, p in zip(init_sol, list_P))
    next_costs = [(-(2 * (k-1) + 1) * p, i) for i, (k, p) in enumerate(zip(init_sol, list_P))]
    heapq.heapify(next_costs)
    while cur_cost > M:
        next_cost, next_idx = heapq.heappop(next_costs)
        
        cur_cost += next_cost
        init_sol[next_idx] -= 1
        if cur_cost <= M:
            break
        heapq.heappush(next_costs, (-(2 * (init_sol[next_idx] - 1) + 1) * list_P[next_idx], next_idx))
    print(sum(init_sol))


solve()

提出情報

提出日時
問題 E - Square Price
ユーザ dinhvietcuong
言語 Python (PyPy 3.10-v7.3.12)
得点 475
コード長 917 Byte
結果 AC
実行時間 234 ms
メモリ 116676 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 475 / 475
結果
AC × 2
AC × 26
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 59 ms 76476 KiB
00_sample_01.txt AC 59 ms 76708 KiB
01_random_00.txt AC 231 ms 116676 KiB
01_random_01.txt AC 234 ms 116392 KiB
01_random_02.txt AC 231 ms 116652 KiB
01_random_03.txt AC 232 ms 116304 KiB
01_random_04.txt AC 234 ms 116288 KiB
01_random_05.txt AC 231 ms 116252 KiB
01_random_06.txt AC 226 ms 116152 KiB
01_random_07.txt AC 232 ms 116456 KiB
01_random_08.txt AC 234 ms 116368 KiB
01_random_09.txt AC 234 ms 116216 KiB
01_random_10.txt AC 109 ms 85588 KiB
01_random_11.txt AC 216 ms 112452 KiB
01_random_12.txt AC 105 ms 84988 KiB
01_random_13.txt AC 122 ms 88324 KiB
01_random_14.txt AC 178 ms 102244 KiB
01_random_15.txt AC 227 ms 115608 KiB
01_random_16.txt AC 157 ms 97100 KiB
01_random_17.txt AC 134 ms 90856 KiB
01_random_18.txt AC 198 ms 108016 KiB
01_random_19.txt AC 213 ms 112076 KiB
01_random_20.txt AC 154 ms 110172 KiB
01_random_21.txt AC 183 ms 115140 KiB
01_random_22.txt AC 60 ms 76640 KiB
01_random_23.txt AC 59 ms 76824 KiB