結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2022-04-06 04:24:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 503 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 79,872 KB |
最終ジャッジ日時 | 2024-11-27 15:02:35 |
合計ジャッジ時間 | 3,110 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 WA * 2 |
ソースコード
INF = 1<<64 N,V = map(int,input().split()) C = list(map(int,input().split())) S = [0] * (N + 1) for i in range(N): S[i+1] = S[i] + C[i] if V <= N: print(S[N]) exit() DP = [INF] * (1<<16) DP[0] = 0 for i in range(1,N+1): for L in range(1<<16): if L - i >= 0: DP[L] = min(DP[L-i] + S[i], DP[L]) V -= N ans = INF for i in range(1,N+1): K = V // i while V - (K * i) <= (1<<12) and K: K -= 1 ans = min(ans, S[i] * K + DP[V - (K * i)] + S[N]) print(ans)