結果

問題 No.409 ダイエット
ユーザー cumin
提出日時 2021-04-26 00:11:08
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 4,753 bytes
コンパイル時間 12,734 ms
コンパイル使用メモリ 284,116 KB
最終ジャッジ日時 2025-01-21 01:00:57
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using Bint = boost::multiprecision::cpp_int;
//#include <atcoder/all>

#define ll long long
#define ld long double

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep2(i, a, b) for(int i = a; i <= b; ++i)
#define rrep(i, a, b) for(int i = a; i >= b; --i)

#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define pld pair<ld,ld>

#define fi first
#define se second

#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define vd vector<double>
#define vll vector<ll>
#define vld vector<ld>
#define vpii vector<pii>
#define vpdd vector<pdd>
#define vpll vector<pll>
#define vpld vector<pld>
#define vvi(a,b,c,d) vector<vector<int>> a(b,vector<int>(c,d));
#define vvll(a,b,c,d) vector<vector<ll>> a(b,vector<ll>(c,d));

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define MAX(x) *max_element(all(x)) 
#define MIN(x) *min_element(all(x)) 
#define sz(a) ((ll)(a).size())

#define endl '\n'
using namespace std;
//using namespace atcoder;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> //切り捨て
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) { //切り上げ
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}
const ll INF=1e18+1;
const int inf=1e9+1;
const double PI=acos(-1);
int dy[8] = {0,1,0,-1,-1,1,1,-1};
int dx[8] = {1,0,-1,0,1,1,-1,-1};

bool range(int y, int x, int h, int w){
  if(y < 0 || x < 0 || y >= h || x >= w) return false;
  else return true;
}

//const int MOD=1000000007;
//using mint = modint1000000007;
//const int MOD=998244353;
//using mint = modint998244353;

const int M = 500001;
using Graph = vector<vector<int>>;

// LiChaoTree
// 直線追加，N個の座標x（昇順）における最小値
// verify: https://judge.yosupo.jp/submission/45842

template<typename T> struct LiChaoTree {
  const T INF = numeric_limits< T >::max() / 2;
  struct Line {
    T a, b;
    Line(T a, T b) : a(a), b(b) {}
    T eval(T x) { return a*x + b; }
  };
  
  int n; //座標の数
  vector< Line > data; //直線群
  vector< T > pos; //i番目の座標x_i
  LiChaoTree(int n) {
    pos.resize(n);
    iota(pos.begin(), pos.end(), 0); //座標圧縮
    init(n);
  }
  LiChaoTree(const vector< T > &pos) : pos(pos) { init(pos.size()); }
  
  void init(int n_){ //2べきにしてる
    n = 1;
    while(n < n_) n <<= 1;
    while((int)pos.size() < n) pos.emplace_back(pos.back() + 1);
    data.assign(n << 1, Line(0, INF));
  }
  
  void add_line(T a, T b){
    Line x(a, b);
    update(1, 0, n-1, x); //[0, n-1]でupdate
  }
  
  inline bool over(Line &a, Line &b, T lb, T ub){
    return a.eval(lb) >= b.eval(lb) && a.eval(ub) >= b.eval(ub); //[lb, ub]で直線aが直線bの上にある
  }
  
  void update(int k, int l, int r, Line &x){
    T lb = pos[l], ub = pos[r];
    if(over(x, data[k], lb, ub)) return;  //加えたいのが完全に上ならなんもしない
    if(over(data[k], x, lb, ub)) {        //加えたいのが完全に下なら変える
      data[k] = x;
      return;
    }
    int c = (l+r) >> 1;
    if(x.eval(pos[c]) < data[k].eval(pos[c])) swap(x, data[k]); //中点で加えたい線が下に来るならswap
    if(x.eval(lb) <= data[k].eval(lb)) update(k << 1|0, l, c, x); //https://smijake3.hatenablog.com/entry/2018/06/16/144548のNo.3
    else update(k << 1|1, c+1, r, x); //https://smijake3.hatenablog.com/entry/2018/06/16/144548のNo.4
  }
  
  T get_min(ll x) { //座標xを含む区間の最小値を計算（子から親へ）
    int i = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
    T res = INF;
    int k = i + n;
    while(k > 0){
      res = min(res, data[k].eval(pos[i]));
      k >>= 1;
    }
    return res;
  }
};
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  cout << fixed << setprecision(15);
  
  ll n, a, b, w;
  cin >> n >> a >> b >> w;
  vll d(n);
  rep(i, n) cin >> d[i];
  vll dp(n+1);
  dp[0] = 0;
  
  vll day(n+1);
  rep(i, n+1) day[i] = (ll)i;
  
  LiChaoTree<ll> LCT(day);
  LCT.add_line(0, 0);
  rep2(i, 1, n){
    dp[i] = LCT.get_min(i) - (ll)a*(i-1) + (ll)((ll)i*i-i)*b/2 + d[i-1];
    LCT.add_line(-(ll)i*b, dp[i] + (ll)i*a + (ll)((ll)i*i+i)*b/2);
  }
  ll ans = INF;
  rep(i, n+1){
    chmin(ans, w + dp[i] - (n-i)*a + ((ll)(n-i)*(n-i+1)/2)*(ll)b);
  }
  cout << ans << endl;
  return 0;
}
0