結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー hitonanode
提出日時 2019-12-16 14:43:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 3,260 bytes
コンパイル時間 1,572 ms
コンパイル使用メモリ 169,588 KB
実行使用メモリ 5,688 KB
最終ジャッジ日時 2024-07-02 19:44:54
合計ジャッジ時間 3,530 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }

// Convex Hull Trick for monotone increasing queries, monotone decreasing slopes
// Each operation is amortized O(1)
// - add_line(a, b): Add `y = ax + b`, a must be monotone decreasing
// - add_convex_parabola(c, a, b): Add `y = c(x - a)^2 + b` (c is constant & a is monotone increasing)
// - get(x): Calculate min/max. value of `y = ax + b`'s at point x, x must be monotone increasing
// - parabola_get(c, x): Caclculate min/max. value of `y = c(x - a)^2 + b`'s
template<typename T_CHT>
struct MonotoneConvexHullTrick : deque<pair<T_CHT, T_CHT>> // (a, b) means `y = ax + b`
{
    using T_MP = __int128_t;
    bool is_minimizer; // If true, this instance calculates min. Otherwise, calculates max.
    MonotoneConvexHullTrick(bool is_minimizer) : is_minimizer(is_minimizer) {}
    void add_line(T_CHT a, T_CHT b) {  // Add y = ax + b
        if (!is_minimizer) a = -a, b = -b;
        while (this->size() > 1u) {
            int sz = this->size();
            __int128_t l = (__int128_t)(this->back().second - (*this)[sz - 2].second) * (this->back().first - a); // Overflow might occur here.
            __int128_t r = (__int128_t)(b - this->back().second) * ((*this)[sz - 2].first - this->back().first);
            if (l < r) break;
            this->pop_back();
        }
        this->emplace_back(a, b);
    }
    T_CHT get(T_CHT x) { 
        while (this->size() > 1u and (*this)[0].first * x + (*this)[0].second > (*this)[1].first * x + (*this)[1].second) {
            this->pop_front();
        }
        return ((*this)[0].first * x + (*this)[0].second) * (is_minimizer ? 1 : -1);
    }
    void add_convex_parabola(T_CHT c, T_CHT a, T_CHT b) { add_line(-2 * c * a, c * a * a + b); } // Add y = c(x - a)^2 + b
    T_CHT parabola_get(T_CHT c, T_CHT x) { return get(x) + c * x * x; }
};


int main()
{
    int N;
    cin >> N;
    vector<lint> A(N);
    cin >> A;
    vector<MonotoneConvexHullTrick<lint>> cht(N + 1, true);
    int x = 0;
    cht[0].add_convex_parabola(1, x, 0);
    REP(i, N) {
        IREP(d, i + 1)
        {
            lint v = cht[d].parabola_get(1, x);
            cht[d + 1].add_convex_parabola(1, x + A[i], v);
        }
        x += A[i];
    }
    IREP(d, N) {
        lint v = cht[d].parabola_get(1, x);
        cout << v << endl;
    }
}
0