#416040 (C++14) No.952 危険な火薬庫

• 問題: No.952 危険な火薬庫
• ユーザー: kcvlex
• 提出日時: 2020-01-13 05:47:15
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,859 bytes
• コンパイル時間: 1,414 ms
• コンパイル使用メモリ: 169,144 KB
• 最終ジャッジ日時: 2024-04-27 03:02:46
• 合計ジャッジ時間: 1,801 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

コンパイルメッセージ

main.cpp: In member function 'i128 ConvexHullTrick::get_query(i128)':
main.cpp:117:23: error: call of overloaded 'abs(i128)' is ambiguous
  117 |         while (2 < abs(right_p - left_p)) {
      |                    ~~~^~~~~~~~~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/cmath:47,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:2:
/usr/include/stdlib.h:848:12: note: candidate: 'int abs(int)'
  848 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~

ソースコード

// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

using i128 = __int128_t;


istream& operator >>(istream &is, i128 &a) {
    int64_t i;
    is >> i;
    a = i;
    return is;
}

ostream& operator <<(ostream &os, i128 a) {
    auto i = (int64_t)a;
    auto j = (int64_t)(a >> 64);
    if (j) os << j;
    os << i;
    return os;
}

const i128 inf = 1e20;

struct ConvexHullTrick {
    using Line = pair<i128, i128>;
    V<Line> lines;
    bool checked;

    ConvexHullTrick() : lines(0), checked(false) {}

    void update_query(Line l) {
        checked = false;
        lines.push_back(l);
    }

    void update_query(i128 a, i128 b) {
        update_query(Line(a, b));
    }

    bool is_necessary(Line a, Line b, Line c) {
        if (a < c) swap(a, c);
        i128 v1 = (c.second - b.second) * (b.first - a.first);
        i128 v2 = (b.second - a.second) * (c.first - b.first);
        return v1 < v2;
    }

    void add_line(i128 a, i128 b) { add_line(Line(a, b)); }

    void add_line(PLL c) {
        while (lines.size() >= 2) {
            auto a = *(lines.end() - 2);
            auto b = *(lines.end() - 1);
            if (!is_necessary(a, b, c)) {
                lines.pop_back();
            } else {
                break;
            }
        }
        lines.push_back(c);
    }

    void check_lines() {
        checked = true;
        sort(ALLR(lines));
        auto tmp = lines;
        lines.clear();
        lines.push_back(tmp[0]);
        lines.push_back(tmp[1]);
        for (i128 i = 2; i < tmp.size(); i++) {
            add_line(tmp[i]);
        }
    }

    i128 get_value(i128 idx, i128 x) {
        if (lines.size() <= idx) return inf;
        i128 a, b;
        tie(a, b) = lines[idx];
        return a * x + b;
    }

    i128 get_query(i128 x) {
        /*
        if (!checked) {
            check_lines();
        }
        */
        i128 left_p = 0, right_p = (ll)lines.size() - 1;
        while (2 < abs(right_p - left_p)) {
            auto mid = (left_p + right_p) / 2;
            auto f1 = get_value(mid, x);
            auto f2 = get_value(mid + 1, x);
            if (f1 < f2) right_p = mid;
            else left_p = mid;
        }
        return var_min(get_value(left_p, x), 
                       get_value(left_p + 1, x),
                       get_value(left_p + 2, x));
    }
};

int main() {
    ll N;
    cin >> N;
    V<ll> A(N);
    for (ll &e : A) cin >> e;
    V<ll> sum(N + 1);
    for (ll i = 0; i < N; i++) sum[i + 1] = sum[i] + A[i];

    auto dp = make_v<i128>(inf, N + 10, N + 10);
    auto pow2 = [](i128 i) { return i * i; };

    dp[0][0] = 0;
    for (ll i = 1; i <= N + 1; i++) {
        dp[i][i - 1] = pow2(sum[i - 1]);
        dp[i][0] = 0;
    }
    for (ll i = 2; i <= N + 1; i++) {
        ConvexHullTrick cht;
        cht.add_line(-2 * sum[i - 1], pow2(sum[i - 1]));
        for (ll j = 0; i + j + 1 <= N + 1; j++) {
            dp[i + j + 1][j + 1] = min(dp[i + j][j + 1], cht.get_query(sum[i + j]) + pow2(sum[i + j]));
            cht.add_line(-2 * sum[i + j], pow2(sum[i + j]) + dp[i + j][j + 1]);
        }
    }

    for (ll i = 1; i <= N; i++) cout << dp[N + 1][i] << endl;
    return 0;
}