結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
![]() |
提出日時 | 2017-02-17 14:26:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,021 bytes |
コンパイル時間 | 632 ms |
コンパイル使用メモリ | 73,052 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 15:53:10 |
合計ジャッジ時間 | 1,309 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> using namespace std; int N; int64_t V; vector<int64_t> C; vector<int64_t> W; // iリトッルを増やすのに必要なコスト int main() { cin >> N >> V; C.resize(N); for(auto &c: C) cin >> c; W = vector<int64_t>(N + 1); for(int i = 0; i < N; i++) { W[i + 1] = W[i] + C[i]; } V -= N; int64_t cost = W[N]; // 全て1L購入する // 貪欲法 // W[i] / iが最小なものを選択する. int min_i = 1; for(int i = 1; i <= N; i++) { // W[min_i] / min_i < W[i] / i if(W[min_i] * i > W[i] * min_i) { min_i = i; } } while(V > 10100) { int64_t t = max<int64_t>(1, (V - 20000) / min_i); V -= t * min_i; cost += t * W[min_i]; } if(V > 0) { // 動的計画法 vector<int64_t> dp(V + 1, 1LL << 60); dp[0] = 0; for(int i = 0; i <= V; i++) { for(int j = 1; j <= N && i + j <= V; j++) { dp[i + j] = min(dp[i + j], dp[i] + W[j]); } } cost += dp[V]; } cout << cost << endl; }