結果
問題 | No.31 悪のミックスジュース |
ユーザー |
|
提出日時 | 2014-09-29 00:41:45 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 100 ms / 5,000 ms |
コード長 | 883 bytes |
コンパイル時間 | 453 ms |
コンパイル使用メモリ | 59,608 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-09-14 15:49:22 |
合計ジャッジ時間 | 2,259 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef unsigned long long ull; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) ull VV[102]; ull dp[1000100]; int main(){ int N,V,C; cin >> N >> V; REP(i,N){ cin >> C; VV[i+1] = C; } REP(i,N) VV[i+1] += VV[i]; V = max(0, V - N); dp[0] = 0; for(int i = 1; i < 1000100; i++){ dp[i] = dp[i-1] + VV[1]; } for(int k = 2; k <= N; k++){ for(int i = k; i < 1000100; i++){ dp[i] = min(dp[i], dp[i-k]+VV[k]); } } int t = 1; for(int i = 2; i <= N; i++){ if(VV[t]*i > VV[i]*t) t = i; } int k = max(0, (V-1000000) / t); ull cost = 0; cost += k * VV[t]; cost += dp[V - k*t]; cost += VV[N]; cout << cost << endl; return 0; }