#1171213 (C++23(gnu拡張gcc16)) No.1077 Noelちゃんと星々4

• 問題: No.1077 Noelちゃんと星々4
• ユーザー: baluteshih
• 提出日時: 2026-07-11 23:34:52
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 3,051 bytes
• コンパイル時間: 5,265 ms
• コンパイル使用メモリ: 357,068 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-11 23:35:00
• 合計ジャッジ時間: 6,642 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 20

ソースコード

#line 1 "test2.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1077"
#line 2 "cplibrary/assumption.hpp"

#include <cassert>
#include <bits/stdc++.h>
#line 3 "test2.cpp"

#line 2 "cplibrary/DataStructure/Convex/SlopeTrick.hpp"

/*
reference: https://maspypy.com/slope-trick-1-解説編
maintaining f(x) = min_f + sum_{l \in pq_l} (l - x) + sum_{r \in pq_r} (x - r)
*/

template<typename T, T INF = std::numeric_limits<T>::max() / 2>
class SlopeTrick {
    using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    using max_heap = std::priority_queue<T>;
    max_heap pq_l;
    min_heap pq_r;
    T top_l() const { return pq_l.empty() ? -INF : pq_l.top() + add_l; }
    T top_r() const { return pq_r.empty() ? INF : pq_r.top() + add_r; }
    T pop_l() { T res = top_l(); if (!pq_l.empty()) pq_l.pop(); return res; }
    T pop_r() { T res = top_r(); if (!pq_r.empty()) pq_r.pop(); return res; }
    void push_l(T a) { pq_l.push(a - add_l); }
    void push_r(T a) { pq_r.push(a - add_r); }
public:
    T add_l, add_r, min_f;
    SlopeTrick() : add_l(), add_r(), min_f() {}
    bool is_inf(T v) { return v >= INF || v <= -INF; }
    int size_l() { return pq_l.size(); }
    int size_r() { return pq_r.size(); }
    int size() { return size_l() + size_r(); }
    T top() { return min_f; }
    std::pair<T, T> top_interval() { return {top_l(), top_r()}; }
    SlopeTrick& add_const(T a) { return min_f += a, *this; }
    // add (x - a)+
    SlopeTrick& add_x_minus_a(T a) {
        min_f += std::max(T(0), top_l() - a);
        push_l(a), push_r(pop_l());
        return *this;
    }
    // add (a - x)+
    SlopeTrick& add_a_minus_x(T a) {
        min_f += std::max(T(0), a - top_r());
        push_r(a), push_l(pop_r());
        return *this;
    }
    // add |x - a|
    SlopeTrick& add_abs(T a) { return add_x_minus_a(a).add_a_minus_x(a); } 
    // add ax + b, O(|a| log n)
    SlopeTrick& add_linear(int a, T b) {
        for (min_f += b; a > 0; --a) {
            T x = pop_l();
            min_f += x, push_r(x);
        }
        for (; a < 0; ++a) {
            T x = pop_r();
            min_f -= x, push_l(x);
        }
    }
    // f(x) = f(x + a)
    void shift(T a) { add_l += a, add_r += a; }
    // g(x) = min_{x-b <= y <= x-a} f(y)
    void sliding_window_minimum(T a, T b) {
        assert(a <= b);
        add_l += a, add_r += b;
    }
    void prefix_min() { min_heap().swap(pq_r); }
    void suffix_min() { max_heap().swap(pq_l); }
    T eval(T x) {
        T res = min_f;
        auto tl = pq_l; auto tr = pq_r;
        for (; !tl.empty(); tl.pop()) res += std::max(T(0), (tl.top() + add_l) - x);
        for (; !tr.empty(); tr.pop()) res += std::max(T(0), x - (tr.top() + add_r));
        return res;
    }
};
#line 5 "test2.cpp"

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    int n;
    std::cin >> n;
    SlopeTrick<int> slope;
    while (n--) {
        int x;
        std::cin >> x;
        slope.prefix_min();
        slope.add_abs(x);
    }
    std::cout << slope.top() << "\n";
}