#839755 (C++17) No.409 ダイエット

• 問題: No.409 ダイエット
• ユーザー: hedwig100
• 提出日時: 2023-02-12 13:41:57
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 90 ms / 2,000 ms
• コード長: 7,258 bytes
• コンパイル時間: 2,344 ms
• コンパイル使用メモリ: 202,960 KB
• 最終ジャッジ日時: 2025-02-10 14:45:02
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 92

ソースコード

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_
void debug_out() {
    cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H << ',';
    debug_out(T...);
}
#define debug(...) cerr << "\033[1;36m" << __func__ << ":L" << __LINE__ << " " << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define dump(x) cerr << __func__ << ":L" << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define irep(i, n) for (int i = (int)(n)-1; i >= 0; --i)

using ll  = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000000'000'000;
constexpr long long MOD  = 1000000007; // = 998244353;
constexpr double EPS     = 1e-6;
constexpr double PI      = 3.14159265358979;

#pragma region Macros
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    for (auto &e : v) {
        os << e << ',';
    }
    os << ']';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        os << *itr << ',';
    }
    os << '}';
    return os;
}
template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> &mp) {
    os << '{';
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        os << itr->first << ": " << itr->second << ',';
    }
    os << '}';
    return os;
}

void yn(bool cond, string Yes = "Yes", string No = "No") {
    cout << (cond ? Yes : No) << '\n';
}

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>
vector<int> id_sort(const vector<T> &A) {
    vector<pair<T, int>> B(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        B[i] = make_pair(A[i], i);
    }
    sort(B.begin(), B.end());
    vector<int> ans(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        ans[i] = B[i].second;
    }
    return ans;
}

#pragma endregion

// 幾何ライブラリのLineと名前が被る恐れがあるのでnamespaceを使う.
namespace _cht {

// Line
// 直線を管理する構造体
template <typename T>
struct Line {
    T a, b;
    Line(T a = 0, T b = 0) : a(a), b(b) {}
    T f(T x) {
        return a * x + b;
    }
    bool operator<(const Line<T> &rhs) const {
        if (a == rhs.a) return (b < rhs.b);
        return (a < rhs.a);
    }

    // necessary
    // l1 <= *this <= l2であり, l1,l2が直線集合にあるときに自分が必要かどうか判定する関数.
    bool neccesary(const Line<T> &l1, const Line<T> &l2) const {
        if (l1.a == a) return false;
        if (l2.a == a) return true;
        return (l2.a - a) * (b - l1.b) < (a - l1.a) * (l2.b - b);
    }
};

// ConvexHullTrickMonotone
// 追加する直線の傾きに単調性がある場合のConvexHullTrick
template <typename T, bool MIN = true>
struct ConvexHullTrickMonotone {
    int n;
    T sgn = MIN ? T(1) : T(-1);
    deque<Line<T>> lines;

    ConvexHullTrickMonotone() : n(0) {
        lines.resize(0);
    }

    // add_right
    // y = ax + bなる直線を追加する.
    // 任意の l \in linesに対して l.a <= a である必要がある.
    // 計算量: 償却 O(1)
    void add_right(T a, T b) {
        if (MIN) return _add_right(a, b);
        return _add_left(a, b);
    }

    // add_left
    // y = ax + bなる直線を追加する.
    // 任意の l \in linesに対して a <= l.a である必要がある.
    // 計算量: 償却 O(1)
    void add_left(T a, T b) {
        if (MIN) return _add_left(a, b);
        return _add_right(a, b);
    }

    // query
    // min_{i=1,\dots,n} a_i x + b_i を求める.
    // 計算量: O(logn)
    // 制約: n > 0,すなわち少なくとも一つ直線が入っている.
    pair<T, Line<T>> query(T x) {
        assert(n > 0);
        int l = 0, r = n;
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (lines[m - 1].f(x) >= lines[m].f(x))
                l = m;
            else
                r = m;
        }
        Line<T> ab(sgn * lines[l].a, sgn * lines[l].b);
        return make_pair(sgn * lines[l].f(x), ab);
    }

    friend ostream &operator<<(ostream &os, const ConvexHullTrickMonotone<T, MIN> &cht) noexcept {
        for (int i = 0; i < cht.n; i++) {
            os << "l(" << cht.lines[i].a << ',' << cht.lines[i].b << "),";
        }
        return os;
    }

  private:
    // _add_right
    // y = ax + bなる直線を追加する.
    // MIN = trueの場合: 任意の l \in linesに対して l.a <= a である必要がある.
    // MIN = falseの場合: 任意の l \in linesに対して a <= l.a である必要がある.
    // 計算量: 償却 O(1)
    void _add_right(T a, T b) {
        Line<T> l(sgn * a, sgn * b);

        if (n <= 1) {
            lines.push_back(l);
            n++;
            return;
        }

        // lは不必要
        if (l.a == lines.back().a && l.b >= lines.back().b)
            return;

        while (n > 1 && !lines.back().neccesary(lines[n - 2], l)) {
            lines.pop_back();
            n--;
        }

        lines.push_back(l);
        n++;
        return;
    }

    // _add_left
    // y = ax + bなる直線を追加する.
    // MIN = true の場合: 任意の l \in linesに対して a <= l.a である必要がある.
    // MIN = false の場合: 任意の l \in linesに対して l.a <= a である必要がある.
    // 計算量: 償却 O(1)
    void _add_left(T a, T b) {
        Line<T> l(sgn * a, sgn * b);

        if (n <= 1) {
            lines.push_front(l);
            n++;
            return;
        }

        // lは不必要
        if (l.a == lines.front().a && l.b >= lines.front().b)
            return;

        while (n > 1 && !lines.front().neccesary(l, lines[1])) {
            lines.pop_front();
            n--;
        }

        lines.push_front(l);
        n++;
        return;
    }
};

} // namespace _cht

using namespace _cht;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int n;
    ll a, b, w;
    cin >> n >> a >> b >> w;
    vector<ll> D(n);
    rep(i, n) cin >> D[i];

    vector<ll> dp(n + 1, 0);
    ConvexHullTrickMonotone<ll, true> cht;

    cht.add_left(0, 0);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = cht.query(i).first + (ll)i * (i - 1) / 2 * b - (i - 1) * a + D[i - 1];
        cht.add_left(-i * b, dp[i] + i * a + (ll)i * (i + 1) * b / 2);
        debug(cht);
    }

    ll ans = HINF;
    rep(i, n + 1) {
        chmin(ans, w + dp[i] - (ll)(n - i) * a + (ll)(n - i) * (n - i + 1) / 2 * b);
        debug(ans);
    }
    cout << ans << '\n';
    return 0;
}