結果

問題 No.703 ゴミ拾い Easy
ユーザー zaki_johozaki_joho
提出日時 2019-10-24 00:25:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,597 bytes
コンパイル時間 1,727 ms
コンパイル使用メモリ 174,756 KB
実行使用メモリ 12,720 KB
最終ジャッジ日時 2023-09-21 20:47:13
合計ジャッジ時間 10,743 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 WA -
testcase_04 AC 1 ms
4,384 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 WA -
testcase_09 AC 2 ms
4,380 KB
testcase_10 WA -
testcase_11 AC 1 ms
4,384 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 WA -
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 296 ms
12,612 KB
testcase_25 AC 296 ms
12,548 KB
testcase_26 AC 295 ms
12,448 KB
testcase_27 AC 296 ms
12,428 KB
testcase_28 AC 297 ms
12,512 KB
testcase_29 AC 297 ms
12,720 KB
testcase_30 AC 296 ms
12,672 KB
testcase_31 AC 296 ms
12,548 KB
testcase_32 AC 296 ms
12,540 KB
testcase_33 AC 296 ms
12,408 KB
testcase_34 AC 218 ms
12,588 KB
testcase_35 AC 217 ms
12,400 KB
testcase_36 AC 217 ms
12,448 KB
testcase_37 AC 221 ms
12,208 KB
testcase_38 AC 217 ms
12,436 KB
testcase_39 AC 223 ms
12,296 KB
testcase_40 AC 217 ms
12,484 KB
testcase_41 AC 217 ms
12,472 KB
testcase_42 AC 217 ms
12,632 KB
testcase_43 AC 217 ms
12,608 KB
testcase_44 AC 1 ms
4,376 KB
testcase_45 AC 1 ms
4,380 KB
testcase_46 AC 286 ms
12,216 KB
testcase_47 AC 275 ms
12,268 KB
testcase_48 AC 2 ms
4,380 KB
testcase_49 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;

// https://github.com/satanic0258/Cpp_snippet/blob/master/src/technique/ConvexHullTrick.cpp
using CHT_TYPE = long long;
class ConvexHullTrickDynamic
{
private:
    // 直線 **************************************************************
    struct Line
    {
        CHT_TYPE a, b;                                // y = ax + b
        mutable std::function<const Line *()> getSuc; // 次の直線へのポインタ (ソートで用いる)

        bool operator<(const Line &rhs) const
        {
            // 取得クエリでは次の直線との差分でソート
            if (rhs.b == IS_QUERY)
            {
                const Line *suc = getSuc();
                if (suc == nullptr)
                    return false;
                const CHT_TYPE &x = rhs.a;
                return (suc->a - a) * x + suc->b - b > 0;
            }
            if (b == IS_QUERY)
            {
                const Line *suc = rhs.getSuc();
                if (suc == nullptr)
                    return true;
                const CHT_TYPE &x = a;
                return (suc->a - rhs.a) * x + suc->b - rhs.b < 0;
            }

            // 通常の直線どうしは傾きソート
            return a < rhs.a;
        }
    };

    // 直線集合 **********************************************************
    class LinesSet : public std::multiset<Line>
    {
    private:
        // true -> 最小値クエリ, false -> 最大値クエリ
        bool flagMin;

    public:
        // コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
        LinesSet(bool flagMin = true) : flagMin(flagMin){};

        // 直線lが不必要であるかどうか
        inline bool isBad(iterator l)
        {
            const auto &&nel = std::next(l);
            if (l == begin())
            { // lが傾き最小のとき
                if (nel == end())
                    return false; // lしかないなら必要
                return l->a == nel->a && l->b <= nel->b;
            }
            else
            {
                const auto &&prl = std::prev(l);
                if (nel == end())
                    return l->a == prl->a && l->b <= prl->b;
                return (prl->b - l->b) * (nel->a - l->a) >= (nel->b - l->b) * (prl->a - l->a);
            }
        }

        // 直線y=ax+bを追加する
        inline void add(CHT_TYPE a, CHT_TYPE b)
        {
            if (flagMin)
                a = -a, b = -b;
            auto &&it = insert({a, b});
            it->getSuc = [=] { return (std::next(it) == end() ? nullptr : &*std::next(it)); };
            if (isBad(it))
            {
                erase(it);
                return;
            }
            while (std::next(it) != end() && isBad(std::next(it)))
                erase(std::next(it));
            while (it != begin() && isBad(std::prev(it)))
                erase(std::prev(it));
        }

        // 直線群の中でxの時に最小(最大)となる値を返す
        inline CHT_TYPE get(CHT_TYPE x)
        {
            auto &&l = *lower_bound(Line{x, IS_QUERY});
            if (flagMin)
                return -l.a * x - l.b;
            else
                return l.a * x + l.b;
        }
    };

    static const CHT_TYPE IS_QUERY = std::numeric_limits<CHT_TYPE>::lowest();
    LinesSet linesSet;

public:
    // コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
    ConvexHullTrickDynamic(bool flagMin = true) : linesSet(flagMin)
    {
        linesSet.add(0, 1e15);
    }
    // 直線y=ax+bを追加する
    inline void add(CHT_TYPE a, CHT_TYPE b) { linesSet.add(a, b); }
    // あるxのときの直線集合での最小値を求める
    inline CHT_TYPE get(CHT_TYPE x) { return linesSet.get(x); }
};

void solve_yukicoder_703()
{
    using ll = long long;
    const ll inf = 1e15;
    int n;
    cin >> n;
    vector<ll> a(n), x(n), y(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> y[i];
    }
    ConvexHullTrickDynamic cht;
    vector<ll> dp(n + 1, inf);
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i + 1] = (a[i] - x[0]) * (a[i] - x[0]) + y[0] * y[0];
        dp[i + 1] = min(dp[i + 1], cht.get(a[i]) + a[i] * a[i]);
        cht.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp[i]);
    }
    cout << dp[n] << endl;
}

int main()
{
    solve_yukicoder_703();
}
0