結果

問題 No.409 ダイエット
コンテスト
ユーザー 0w1
提出日時 2019-11-26 12:13:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 832 bytes
コンパイル時間 549 ms
コンパイル使用メモリ 66,984 KB
最終ジャッジ日時 2025-01-08 05:38:46
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using namespace std;

long long find_min(int, long long *);
long long int n, a, b, w;
int temp = 0, brk = 0;

int main() {
  // input
  cin >> n >> a >> b >> w;

  int *D = new int[n];
  for (int i = 0; i < n; i++) cin >> D[i];

  // output when b = 0
  if (b == 0) {
    cout << w - a * n << endl;
    return 0;
  }

  long long *zero = new long long[n + 1];
  zero[0] = 0;

  for (int i = 0; i < n; i++) zero[i + 1] = find_min(i, zero) + D[i];
  cout << w + find_min(n, zero) << endl;
}

long long find_min(int i, long long *zero) {
  if (i <= 0) return 0;
  long long min = zero[i], total;  // *zero DISP -- 1
  for (int k = 1; k <= i; k++) {
    total = zero[i - k] - a * k + b * (1 + k) * k / 2;
    if (total < min) min = total, brk = i - k;
    if (i - k < temp) break;
  }
  temp = brk;
  return min;
}
0