結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
![]() |
提出日時 | 2022-04-04 18:01:58 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 544 bytes |
コンパイル時間 | 138 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 70,924 KB |
最終ジャッジ日時 | 2024-11-25 09:58:47 |
合計ジャッジ時間 | 1,684 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 9 |
ソースコード
INF = 1<<64 N,V = map(int,input().split()) C = list(map(int,input().split())) S = [0] * N for i in range(N): S[i] = S[i-1] + C[i] if V <= N: print(S[-1]) exit() DP = [[INF] * 101 for _ in range(N+1)] DP[0][0] = 0 for i in range(N): for j in range(101): DP[i+1][j] = min(DP[i][j], DP[i+1][j]) k = min(100, (i + 1) + j) DP[i+1][k] = min(DP[i][j] + S[i], DP[i+1][j] + S[i], DP[i+1][k]) V -= N ans = INF for i in range(N): ans = min(ans, (S[i] * (V // (i + 1))) + (DP[N][V % (i + 1)]) + S[-1]) print(ans)