test/yuki/yuki_409.test.cpp

• View this file on GitHub
• Last update: 2023-07-05 22:32:04+09:00
• Problem: https://yukicoder.me/problems/no/409

Depends on

• Convex Hull Trick (algorithm/convex_hull_trick.hpp)

Code

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

#include <algorithm>
#include <cstdint>
#include <iostream>

#include "../../algorithm/convex_hull_trick.hpp"

using i64 = std::int64_t;

int main() {
    int n;
    i64 a, b, w;
    std::cin >> n >> a >> b >> w;
    ebi::convex_hull_trick<i64> cht;
    cht.add(-2 * a - b, 2 * w + 2 * a);
    auto f = [&](i64 r) -> i64 { return -a * r + b * r * (r + 1) / 2; };
    i64 ans = w + f(n);
    for (int i = 1; i <= n; i++) {
        i64 d;
        std::cin >> d;
        i64 val = cht.min(i);
        i64 res = b * i * i + 2 * d + val;
        res /= 2;
        cht.add(-2 * a - 2 * b * i - b,
                b * i * i + b * i + 2 * a * (i + 1) + 2 * res);
        ans = std::min(ans, res + f(n - i));
    }
    std::cout << ans << '\n';
}

#line 1 "test/yuki/yuki_409.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/409"

#include <algorithm>
#include <cstdint>
#include <iostream>

#line 2 "algorithm/convex_hull_trick.hpp"

#include <cassert>
#include <deque>
#include <utility>

namespace ebi {

template <class T> struct convex_hull_trick {
  private:
    bool check(std::pair<T, T> a, std::pair<T, T> b, std::pair<T, T> c) {
        return (b.first - a.first) * (c.second - b.second) >=
               (c.first - b.first) * (b.second - a.second);
    }

    T f(std::pair<T, T> a, T x) {
        return a.first * x + a.second;
    }

  public:
    convex_hull_trick() = default;

    void add(T a, T b) {
        while (lines.size() >= 2 &&
               check(*(lines.end() - 2), lines.back(), {a, b})) {
            lines.pop_back();
        }
        lines.emplace_back(a, b);
    }

    T min(T x) {
        assert(!lines.empty());
        while (lines.size() >= 2 && f(lines[0], x) >= f(lines[1], x)) {
            lines.pop_front();
        }
        return f(lines[0], x);
    }

  private:
    std::deque<std::pair<T, T>> lines;
};

}  // namespace ebi
#line 8 "test/yuki/yuki_409.test.cpp"

using i64 = std::int64_t;

int main() {
    int n;
    i64 a, b, w;
    std::cin >> n >> a >> b >> w;
    ebi::convex_hull_trick<i64> cht;
    cht.add(-2 * a - b, 2 * w + 2 * a);
    auto f = [&](i64 r) -> i64 { return -a * r + b * r * (r + 1) / 2; };
    i64 ans = w + f(n);
    for (int i = 1; i <= n; i++) {
        i64 d;
        std::cin >> d;
        i64 val = cht.min(i);
        i64 res = b * i * i + 2 * d + val;
        res /= 2;
        cht.add(-2 * a - 2 * b * i - b,
                b * i * i + b * i + 2 * a * (i + 1) + 2 * res);
        ans = std::min(ans, res + f(n - i));
    }
    std::cout << ans << '\n';
}

Back to top page