結果

問題 No.409 ダイエット
コンテスト
ユーザー 0w1
提出日時 2019-10-17 14:12:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 867 bytes
コンパイル時間 1,934 ms
コンパイル使用メモリ 198,880 KB
最終ジャッジ日時 2025-01-07 22:05:59
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 35 RE * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, A, B, W;
  cin >> N >> A >> B >> W;

  vector<int> D(N);
  for (int i = 0; i < N; ++i) {
    cin >> D[i];
  }

  if (B == 0) {
    int64_t ans = W - (int64_t) N * A;
    cout << ans << endl;
  } else {
    int maxd = *max_element(D.begin(), D.end());
    int threshold = ceil(2 * sqrt((maxd + A) / (3 * B)));

    const int64_t INF = 3e11;
    vector<vector<int64_t>> dp(N + 1, vector<int64_t>(threshold, 3e11));
    dp[0][0] = W;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < threshold; ++j) {
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + D[i]);
        if (j + 1 < threshold) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] - A + (int64_t) B * (j + 1));
      }
    }

    int64_t ans = *min_element(dp[N].begin(), dp[N].end());
    cout << ans << endl;
  }

  return 0;
}
0