結果

問題 No.703 ゴミ拾い Easy
ユーザー zaki_johozaki_joho
提出日時 2019-10-24 01:02:50
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 295 ms / 1,500 ms
コード長 3,684 bytes
コンパイル時間 1,776 ms
コンパイル使用メモリ 175,148 KB
実行使用メモリ 12,732 KB
最終ジャッジ日時 2023-08-30 19:11:56
合計ジャッジ時間 9,933 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 294 ms
12,396 KB
testcase_25 AC 294 ms
12,628 KB
testcase_26 AC 294 ms
12,488 KB
testcase_27 AC 293 ms
12,536 KB
testcase_28 AC 295 ms
12,624 KB
testcase_29 AC 295 ms
12,732 KB
testcase_30 AC 294 ms
12,488 KB
testcase_31 AC 295 ms
12,608 KB
testcase_32 AC 294 ms
12,468 KB
testcase_33 AC 293 ms
12,444 KB
testcase_34 AC 217 ms
12,648 KB
testcase_35 AC 217 ms
12,248 KB
testcase_36 AC 215 ms
12,612 KB
testcase_37 AC 217 ms
12,244 KB
testcase_38 AC 218 ms
12,356 KB
testcase_39 AC 217 ms
12,488 KB
testcase_40 AC 216 ms
12,392 KB
testcase_41 AC 216 ms
12,232 KB
testcase_42 AC 216 ms
12,488 KB
testcase_43 AC 217 ms
12,392 KB
testcase_44 AC 1 ms
4,380 KB
testcase_45 AC 2 ms
4,380 KB
testcase_46 AC 283 ms
12,292 KB
testcase_47 AC 270 ms
12,276 KB
testcase_48 AC 2 ms
4,380 KB
testcase_49 AC 3 ms
4,376 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) {}
	// 直線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+1), x(n+1), y(n+1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> y[i];
    }
    ConvexHullTrickDynamic cht;
    vector<ll> dp(n + 1, inf);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cht.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp[i-1]);
        dp[i] = cht.get(a[i]) + a[i] * a[i];
        //cerr << dp[i] << endl;
    }
    cout << dp[n] << endl;
}

int main()
{
    solve_yukicoder_703();
}
0