結果

問題 No.409 ダイエット
ユーザー tokusakurai
提出日時 2020-09-02 10:07:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 2,681 bytes
コンパイル時間 2,948 ms
コンパイル使用メモリ 201,456 KB
最終ジャッジ日時 2025-01-14 03:32:36
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<typename T, bool ismin = true>
struct Convex_Hull_Trick{
    vector<T> a, b; //y = ax+b
    deque<int> que;

    Convex_Hull_Trick() = default;

    bool empty() const {return que.empty();}

    T f(int i, T x) {return a[i]*x+b[i];}

    bool judge(int i, int j, int k){
        return (b[k]-b[j])*(a[j]-a[i]) >= (b[j]-b[i])*(a[k]-a[j]);
    }

    void add_line(T p, T q){
        if(!ismin) p *= -1, q *= -1;
        assert(empty() || a.back() >= p);
        int k = sz(a);
        a.pb(p), b.pb(q);
        if(!que.empty() && a[que.back()] == p){
            if(b[que.back()] <= q) return;
            que.pop_back();
        }
        while(sz(que) >= 2 && judge(que[sz(que)-2], que[sz(que)-1], k)) que.pop_back();
        que.push_back(k);
    }

    T query(T x){
        assert(!empty());
        int l = 0, r = sz(que);
        while(r-l > 1){
            int m = (l+r)/2;
            (f(que[m-1], x) >= f(que[m], x)? l : r) = m;
        }
        return ismin? f(que[l], x) : -f(que[l], x);
    }

    T query_monotone_inc(T x){
        assert(!empty());
        while(sz(que) >= 2 && f(que[0], x) >= f(que[1], x)) que.pop_front();
        return ismin? f(que[0], x) : -f(que[0], x);
    }

    T query_monotone_dec(T x){
        assert(!empty());
        while(sz(que) >= 2 && f(que[sz(que)-1], x) >= f(que[sz(que)-2], x)) que.pop_back();
        return ismin? f(que[sz(que)-1], x) : -f(que[sz(que)-1], x);
    }
};

int main(){
    int N;
    ll A, B, W;
    cin >> N >> A >> B >> W;
    Convex_Hull_Trick<ll> cht;
    ll dp[N+2];
    dp[0] = 2*W;
    cht.add_line(-2*A-B, dp[0]+2*A);
    for(ll i = 1; i <= N+1; i++){
        ll D = 0;
        if(i <= N) cin >> D;
        dp[i] = cht.query_monotone_inc(i)+2*D+B*i*i;
        cht.add_line(-2*A-B*(2*i+1), dp[i]+2*A*(i+1)+B*i*(i+1));
    }
    cout << dp[N+1]/2 << endl;
}
0