結果

問題 No.409 ダイエット
ユーザー 0w1
提出日時 2019-11-26 11:50:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 904 bytes
コンパイル時間 1,026 ms
コンパイル使用メモリ 76,884 KB
最終ジャッジ日時 2025-01-08 05:38:25
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 44 WA * 15 RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <queue>
using namespace std;
struct mat {
  int i;
  int X;
  long long w;
};

int main() {
  int N, A, B, W;
  long long ans;
  cin >> N >> A >> B >> W;
  int D[N];
  for (int i = 0; i < N; i++) {
    cin >> D[i];
  }
  queue<mat> v;
  struct mat d1ST = {0, 1, W + B - A};
  struct mat d1SL = {0, 0, W + D[0]};
  ans = (d1SL.w < d1ST.w) ? d1SL.w : d1ST.w;
  int minSleep;
  if (N > 1) {
    v.push(d1ST);
    v.push(d1SL);
    minSleep = W + D[0];
  }
  for (int i = 1; i < N; i++) {
    minSleep = ans + D[i];
    ans += D[i];
    while (v.front().i == i - 1) {
      struct mat tmp = v.front();
      v.pop();
      struct mat st = {i, tmp.X + 1, tmp.w + (tmp.X + 1) * B - A};

      if (st.w < minSleep) {
        if (st.w < ans) ans = st.w;
        v.push(st);
      }
    }
    struct mat mS = {i, 0, minSleep};
    v.push(mS);
  }
  cout << ans << endl;
  return 0;
}
0