結果

問題 No.1782 ManyCoins
ユーザー tamato
提出日時 2021-12-12 19:03:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,190 ms / 2,000 ms
コード長 987 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 113,536 KB
最終ジャッジ日時 2024-07-21 06:39:30
合計ジャッジ時間 13,979 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9
inf = 10 ** 18


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, L = map(int, input().split())
    W = list(map(int, input().split()))

    W.sort()
    w_max = W[-1]

    seen = [inf] * w_max
    que = deque([(0, 0)])
    seen[0] = 0
    while que:
        v, d = que.popleft()
        if d != seen[v]:
            continue
        for w in W[:-1]:
            u = v + w
            if u < w_max:
                if d < seen[u]:
                    seen[u] = d
                    que.appendleft((u, d))
            else:
                u -= w_max
                if d + 1 < seen[u]:
                    seen[u] = d + 1
                    que.append((u, d + 1))

    ans = 0
    for i in range(w_max):
        add = L // w_max
        if i:
            if L % w_max >= i:
                add += 1
        add -= seen[i]
        ans += max(0, add)
    print(ans)


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