結果

問題 No.31 悪のミックスジュース
コンテスト
ユーザー rpy3cpp
提出日時 2015-09-02 08:07:37
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,462 bytes
コンパイル時間 82 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-18 17:34:56
合計ジャッジ時間 1,477 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools


def read_data():
    N, V = map(int, input().split())
    Cs = list(map(int, input().split()))
    return N, V, Cs


def select_most_efficient(Ds):
    n = 0
    cost = 1
    records = []
    for k, d in enumerate(Ds, 1):
        det = k * cost - n * d
        if det > 0:
            n = k
            cost = d
            records = [k - 1]
        elif det == 0:
            records.append(k - 1)
    return records


def solve(N, V, Cs):
    if V <= N:
        return sum(Cs)
    if N == 1:
        return Cs[0] * V
    V -= N
    Ds = list(itertools.accumulate(Cs))
    effs = select_most_efficient(Ds)
    min_cost = Cs[0] * V
    for idx in effs:
        cost = calc_cost(V, Cs, Ds, idx)
        if cost < min_cost:
            min_cost = cost
    return min_cost + sum(Cs)


def calc_cost(V, Cs, Ds, idx):
    m, r = divmod(V, idx + 1)
    cost = Ds[idx] * m
    if r == 0:
        return cost
    dp_head = get_dp(r, r, Cs[:r])
    if m == 0 or idx == len(Ds) - 1:
        return cost + dp_head[r]
    dp_tail = get_dp(r, m, Cs[idx + 1:])
    return cost + min(a + b for a, b in zip(dp_head[::-1], dp_tail))


def get_dp(r, m, Cs):
    Ds = itertools.accumulate(Cs)
    dp = [0] + [float('inf')] * r
    for i, d in enumerate(Ds, 1):
        if i > m or i > r:
            break
        for j in range(i, min(r, m * i) + 1, i):
            dp[j] = min(dp[j], dp[j - i] + d)
    return dp

N, V, Cs = read_data()
print(solve(N, V, Cs))
0