#265997 (C++14) No.703 ゴミ拾い Easy

提出ソース

結果

問題	No.703 ゴミ拾い Easy
ユーザー	anta
提出日時	2018-06-15 22:47:26
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	226 ms / 1,500 ms
コード長	3,470 bytes
コンパイル時間	2,179 ms
コンパイル使用メモリ	185,708 KB
実行使用メモリ	30,932 KB
最終ジャッジ日時	2024-06-10 18:32:06
合計ジャッジ時間	8,426 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	3 ms 6,944 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	3 ms 6,944 KB
testcase_19	AC	3 ms 6,940 KB
testcase_20	AC	3 ms 6,944 KB
testcase_21	AC	3 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	3 ms 6,940 KB
testcase_24	AC	221 ms 29,116 KB
testcase_25	AC	224 ms 29,376 KB
testcase_26	AC	222 ms 30,660 KB
testcase_27	AC	219 ms 28,140 KB
testcase_28	AC	224 ms 27,616 KB
testcase_29	AC	224 ms 29,628 KB
testcase_30	AC	221 ms 29,192 KB
testcase_31	AC	223 ms 29,600 KB
testcase_32	AC	219 ms 29,612 KB
testcase_33	AC	226 ms 30,932 KB
testcase_34	AC	171 ms 30,632 KB
testcase_35	AC	171 ms 28,168 KB
testcase_36	AC	169 ms 29,908 KB
testcase_37	AC	167 ms 27,928 KB
testcase_38	AC	172 ms 29,448 KB
testcase_39	AC	170 ms 30,108 KB
testcase_40	AC	168 ms 27,992 KB
testcase_41	AC	170 ms 27,736 KB
testcase_42	AC	170 ms 28,136 KB
testcase_43	AC	170 ms 28,544 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	179 ms 29,332 KB
testcase_47	AC	183 ms 28,776 KB
testcase_48	AC	3 ms 6,944 KB
testcase_49	AC	3 ms 6,948 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
	}
}

yukicoder

結果

テストケース

ソースコード