結果

問題 No.703 ゴミ拾い Easy
ユーザー antaanta
提出日時 2018-06-15 22:47:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 214 ms / 1,500 ms
コード長 3,470 bytes
コンパイル時間 1,920 ms
コンパイル使用メモリ 182,416 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2023-08-30 18:58:20
合計ジャッジ時間 8,418 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 212 ms
29,944 KB
testcase_25 AC 212 ms
29,028 KB
testcase_26 AC 212 ms
29,408 KB
testcase_27 AC 213 ms
29,076 KB
testcase_28 AC 213 ms
29,180 KB
testcase_29 AC 211 ms
27,960 KB
testcase_30 AC 213 ms
28,132 KB
testcase_31 AC 214 ms
30,132 KB
testcase_32 AC 214 ms
29,568 KB
testcase_33 AC 212 ms
28,424 KB
testcase_34 AC 157 ms
28,192 KB
testcase_35 AC 160 ms
28,168 KB
testcase_36 AC 159 ms
29,152 KB
testcase_37 AC 160 ms
29,436 KB
testcase_38 AC 160 ms
30,592 KB
testcase_39 AC 160 ms
29,456 KB
testcase_40 AC 160 ms
29,440 KB
testcase_41 AC 159 ms
29,268 KB
testcase_42 AC 158 ms
28,356 KB
testcase_43 AC 160 ms
28,740 KB
testcase_44 AC 2 ms
4,380 KB
testcase_45 AC 1 ms
4,376 KB
testcase_46 AC 176 ms
29,328 KB
testcase_47 AC 173 ms
29,948 KB
testcase_48 AC 2 ms
4,376 KB
testcase_49 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include "bits/stdc++.h"
using namespace std;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }

struct IncrementalEnvelope {
	typedef pair<int, long long> P;
	typedef int X;
	vector<P> ps;
	vector<pair<X, P> > seq;
	vector<int> sizes;

	void clear() {
		ps.clear();
		seq.clear();
		sizes.clear();
	}

	bool empty() const { return ps.empty(); }

	struct ComparePoint {
		bool operator()(const P &a, const P &b) const {
			if (a.first != b.first)
				return a.first < b.first;
			else
				return a.second > b.second;
		}
	};

	void insert(const P &p) {
		int n = (int)ps.size();
		ps.push_back(p);
		seq.push_back(make_pair(-1, P()));
		int i;
		for (i = 0; n >> i & 1; ++ i) {
			int m = 1 << i;
			inplace_merge(ps.end() - m * 2, ps.end() - m, ps.end(), ComparePoint());
			sizes[i] = 0;
		}
		if (sizes.size() == i)
			sizes.push_back(0);
		assert(sizes[i] == 0);
		int m = 1 << i;
		makeEnvelope(&*(seq.end() - m), sizes[i], &*(ps.end() - m), &ps[0] + ps.size());
	}

	long long findMax(X x) const {
		long long r = numeric_limits<long long>::min();
		const pair<X, P> *stk = &seq[0] + seq.size();
		for (int i = 0; i < (int)sizes.size(); ++ i) {
			int n = sizes[i];
			if (n != 0) {
				stk -= 1 << i;
				long long val = findMaxEnvelope(stk, n, x);
				if (r < val)
					r = val;
			}
		}
		return r;
	}

private:
	static long long findMaxEnvelope(const pair<X, P> *stk, int size, X x) {
		int l = 0, u = size - 1;
		while (u - l > 0) {
			int mid = (l + u + 1) / 2;
			if (stk[mid].first <= x)
				l = mid;
			else
				u = mid - 1;
		}
		P p = stk[l].second;
		return evaluate(p, x);
	}

	static void makeEnvelope(pair<X, P> *stk, int &sp, const P *begin, const P *end) {
		sp = 0;
		for (const P *it = begin; it != end; ++ it) {
			P p = *it;
			if (sp > 0 && p.first == stk[sp - 1].second.first)
				continue;
			for (; sp > 0; -- sp) {
				X x = stk[sp - 1].first;
				if (evaluate(p, x) <= evaluate(stk[sp - 1].second, x))
					break;
			}
			long long x;
			if (sp == 0)
				x = 0;
			else
				x = crosspoint(stk[sp - 1].second, p);
			assert(x >= 0);
			if (x > numeric_limits<X>::max())
				x = numeric_limits<X>::max();
			stk[sp ++] = make_pair((X)x, p);
		}
	}

	static long long evaluate(const P &p, X x) {
		return (long long)x * p.first + p.second;
	}

	static long long crosspoint(const P &p, const P &q) {
		long long num = p.second - q.second;
		int den = q.first - p.first;
		assert(den > 0);
		return (num / den + (num > 0 && num % den != 0));
	}

public:
	void swap(IncrementalEnvelope &that) {
		ps.swap(that.ps);
		seq.swap(that.seq);
		sizes.swap(that.sizes);
	}
};

int main() {
	int N;
	while (~scanf("%d", &N)) {
		vector<int> as(N);
		for (int i = 0; i < N; ++ i)
			scanf("%d", &as[i]);
		vector<int> xs(N);
		for (int i = 0; i < N; ++ i)
			scanf("%d", &xs[i]);
		vector<int> ys(N);
		for (int i = 0; i < N; ++ i)
			scanf("%d", &ys[i]);
		auto sq = [](int x) {return (long long)x * x; };
		const long long INFL = 0x3f3f3f3f3f3f3f3fLL;;
		vector<long long> dp(N + 1, INFL);
		dp[0] = 0;
		IncrementalEnvelope envelope;
		for (int i = 0; i < N; ++ i) {
			envelope.insert(IncrementalEnvelope::P(2 * xs[i], -(dp[i] + sq(ys[i]) + sq(xs[i]))));
			long long t = INFL;
//			for (int j = 0; j <= i; ++ j)
//				amin(t, dp[j] + sq(ys[j]) + sq(as[i]) + sq(xs[j]) - 2LL * as[i] * xs[j]);
			t = -envelope.findMax(as[i]) + sq(as[i]);
			dp[i + 1] = t;
		}
		long long ans = dp[N];
		printf("%lld\n", ans);
	}
}
0