結果

問題 No.31 悪のミックスジュース
ユーザー r_dream0r_dream0
提出日時 2017-02-17 14:23:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,021 bytes
コンパイル時間 711 ms
コンパイル使用メモリ 71,168 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-09 20:49:05
合計ジャッジ時間 1,423 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
5,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
5,376 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 max_i = 1;
  for(int i = 1; i <= N; i++) {
    // W[max_i] / max_i < W[i] / i
    if(W[max_i] * i < W[i] * max_i) {
      max_i = i;
    }
  }
  while(V > 10100) {
    int64_t t = max<int64_t>(1, (V - 20000) / max_i);
    V -= t * max_i;
    cost += t * W[max_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;
}
0