結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2015-02-15 15:15:34 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 585 ms / 5,000 ms |
コード長 | 437 bytes |
コンパイル時間 | 449 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 6,784 KB |
最終ジャッジ日時 | 2024-09-14 15:49:52 |
合計ジャッジ時間 | 3,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
N,V=map(int,raw_input().split()) C=map(int,raw_input().split()) s=0 S=[] A=[] for i in range(N): s+=C[i] S.append(s) A.append((s/(1.0+i),i)) A.sort() m=A[0][1]+1 dp=[m*N*1000000000 for i in range(m*N+1)] dp[0]=0 for i in range(N): for j in range(m*N+1): if i+j+1 >=m*N+1: continue dp[i+j+1]=min(dp[i+j+1],dp[j]+S[i]) v = V-N t = max(0, (v-m*N+m-1)/m) print s+t*S[A[0][1]]+dp[max(0,v-t*m)]