結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
![]() |
提出日時 | 2020-03-31 13:51:57 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 376 ms / 5,000 ms |
コード長 | 620 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-06-24 10:20:20 |
合計ジャッジ時間 | 5,074 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import itertools N, V, *C = map(int, read().split()) C = tuple(itertools.accumulate(C)) V -= N answer = C[-1] U = 10010 # cost -> value INF = 10 ** 18 dp = [INF] * U dp[0] = 0 for i, x in enumerate(C, 1): for j in range(i, U): c = dp[j - i] + x if dp[j] > c: dp[j] = c rate = [x / i for i, x in enumerate(C, 1)] n = rate.index(min(rate)) + 1 k = max(0, 1 + (V - U) // n) answer += k * C[n - 1] if V > 0: answer += dp[V - k * n] print(answer)