Test/DataStructure/ConvexHullTrick.test.cpp

• View this file on GitHub
• Last update: 2024-11-12 00:26:16+09:00
• Problem: https://yukicoder.me/problems/no/409

Depends on

• Library/DataStructure/ConvecHullTrick.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/409"

#include <iostream>

#include <numeric>

#include <vector>


#include "./../../Library/DataStructure/ConvecHullTrick.hpp"


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n, a, b, w;
  cin >> n >> a >> b >> w;
  std::vector<ll> d;
  d.reserve(n);
  for (int i = 0; i < n; ++i) {
    ll x;
    cin >> x;
    d.emplace_back(x);
  }

  constexpr ll mx = 1e18;
  auto cht = mtd::ConvexHullTrick();
  std::vector<ll> dp(n + 1, mx);
  auto update = [&](ll i, ll x) {
    dp[i] = x;
    auto pa = -b * i;
    auto pb = a * i + i * (i + 1) / 2 * b + dp[i];
    cht.add(pa, pb);
  };

  update(0, w);
  for (ll i = 1; i < n + 1; ++i) {
    auto ad = d[i - 1] - a * i + a + i * (i - 1) / 2 * b;
    auto min = cht.query(i);
    update(i, ad + min);
  }

  ll ans = dp[n];
  for (ll i = 0; i < n; ++i) {
    ll k = n - i;
    ans = std::min(ans, dp[i] + -a * k + k * (k + 1) / 2 * b);
  }

  cout << ans << endl;
}

#line 1 "Test/DataStructure/ConvexHullTrick.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/409"

#include <iostream>

#include <numeric>

#include <vector>


#line 2 "Library/DataStructure/ConvecHullTrick.hpp"

#include <deque>


namespace mtd {
  /*
   * 直線は傾きについて広義単調減少(最大値クエリの場合は広義単調増加)
   * クエリは広義単調増加
   */
  class ConvexHullTrick {
    using T = long long;
    std::deque<std::pair<T, T>> lines;

    static auto func(const std::pair<T, T>& line, const T& x) {
      return x * line.first + line.second;
    }
    static auto check(const std::pair<T, T>& line1,
                      const std::pair<T, T>& line2,
                      const std::pair<T, T>& line3) {
      auto [a1, b1] = line1;
      auto [a2, b2] = line2;
      auto [a3, b3] = line3;
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);
    }

  public:
    ConvexHullTrick() {}

    auto add(const std::pair<T, T>& line) {
      while (lines.size() > 1 &&
             check(*std::next(lines.rbegin()), *lines.rbegin(), line)) {
        lines.pop_back();
      }
      lines.emplace_back(line);
    }
    auto add(const T& a, const T& b) { add({a, b}); }

    auto query(const T& x) {
      while (lines.size() > 1 &&
             func(*lines.begin(), x) > func(*std::next(lines.begin()), x)) {
        lines.pop_front();
      }
      return func(*lines.begin(), x);
    }
  };
}  // namespace mtd

#line 8 "Test/DataStructure/ConvexHullTrick.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n, a, b, w;
  cin >> n >> a >> b >> w;
  std::vector<ll> d;
  d.reserve(n);
  for (int i = 0; i < n; ++i) {
    ll x;
    cin >> x;
    d.emplace_back(x);
  }

  constexpr ll mx = 1e18;
  auto cht = mtd::ConvexHullTrick();
  std::vector<ll> dp(n + 1, mx);
  auto update = [&](ll i, ll x) {
    dp[i] = x;
    auto pa = -b * i;
    auto pb = a * i + i * (i + 1) / 2 * b + dp[i];
    cht.add(pa, pb);
  };

  update(0, w);
  for (ll i = 1; i < n + 1; ++i) {
    auto ad = d[i - 1] - a * i + a + i * (i - 1) / 2 * b;
    auto min = cht.query(i);
    update(i, ad + min);
  }

  ll ans = dp[n];
  for (ll i = 0; i < n; ++i) {
    ll k = n - i;
    ans = std::min(ans, dp[i] + -a * k + k * (k + 1) / 2 * b);
  }

  cout << ans << endl;
}

Back to top page