結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー anta
提出日時 2018-06-15 22:47:26
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 216 ms / 1,500 ms
コード長 3,470 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,913 ms
コンパイル使用メモリ 179,164 KB
実行使用メモリ 29,136 KB
最終ジャッジ日時 2025-01-02 13:55:29
合計ジャッジ時間 8,433 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:122:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  122 |                         scanf("%d", &as[i]);
      |                         ~~~~~^~~~~~~~~~~~~~
main.cpp:125:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  125 |                         scanf("%d", &xs[i]);
      |                         ~~~~~^~~~~~~~~~~~~~
main.cpp:128:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |                         scanf("%d", &ys[i]);
      |                         ~~~~~^~~~~~~~~~~~~~

ソースコード

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