test/convex_hull_trick_monotone.test.cpp

• View this file on GitHub
• Last update: 2023-02-12 13:47:58+09:00
• Problem: https://yukicoder.me/problems/no/409

Depends on

• data_structures/convex_hull_trick.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://yukicoder.me/problems/no/409"
#include "../data_structures/convex_hull_trick.cpp"
#include "../template/const.hpp"

using ll = long long;

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);
    for (int i = 0; i < n; i++)
        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);
    }

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

#line 1 "test/convex_hull_trick_monotone.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://yukicoder.me/problems/no/409"
#line 3 "data_structures/convex_hull_trick.cpp"
using namespace std;

// 幾何ライブラリの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;
#line 2 "template/const.hpp"
constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000'000'000'000;
constexpr long long MOD  = 998244353;
constexpr double EPS     = 1e-6;
constexpr double PI      = 3.14159265358979;
#line 7 "test/convex_hull_trick_monotone.test.cpp"

using ll = long long;

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);
    for (int i = 0; i < n; i++)
        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);
    }

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

Back to top page