結果

問題 No.703 ゴミ拾い Easy
ユーザー snrnsidysnrnsidy
提出日時 2023-04-17 13:11:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 173 ms / 1,500 ms
コード長 5,906 bytes
コンパイル時間 4,059 ms
コンパイル使用メモリ 368,212 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-10-12 14:22:26
合計ジャッジ時間 8,918 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,760 KB
testcase_01 AC 5 ms
5,760 KB
testcase_02 AC 4 ms
5,888 KB
testcase_03 AC 5 ms
5,760 KB
testcase_04 AC 4 ms
5,760 KB
testcase_05 AC 4 ms
5,888 KB
testcase_06 AC 5 ms
5,760 KB
testcase_07 AC 4 ms
5,888 KB
testcase_08 AC 5 ms
5,760 KB
testcase_09 AC 4 ms
5,888 KB
testcase_10 AC 4 ms
5,760 KB
testcase_11 AC 4 ms
5,760 KB
testcase_12 AC 4 ms
5,760 KB
testcase_13 AC 5 ms
5,888 KB
testcase_14 AC 5 ms
5,760 KB
testcase_15 AC 5 ms
5,760 KB
testcase_16 AC 5 ms
5,888 KB
testcase_17 AC 4 ms
6,016 KB
testcase_18 AC 5 ms
5,888 KB
testcase_19 AC 5 ms
5,760 KB
testcase_20 AC 5 ms
6,016 KB
testcase_21 AC 6 ms
5,760 KB
testcase_22 AC 5 ms
5,888 KB
testcase_23 AC 5 ms
6,016 KB
testcase_24 AC 152 ms
12,928 KB
testcase_25 AC 147 ms
13,056 KB
testcase_26 AC 173 ms
12,928 KB
testcase_27 AC 138 ms
12,892 KB
testcase_28 AC 138 ms
13,016 KB
testcase_29 AC 139 ms
13,028 KB
testcase_30 AC 134 ms
12,928 KB
testcase_31 AC 134 ms
12,928 KB
testcase_32 AC 134 ms
12,928 KB
testcase_33 AC 138 ms
13,024 KB
testcase_34 AC 77 ms
12,892 KB
testcase_35 AC 79 ms
12,800 KB
testcase_36 AC 77 ms
12,800 KB
testcase_37 AC 77 ms
12,768 KB
testcase_38 AC 76 ms
12,800 KB
testcase_39 AC 76 ms
12,800 KB
testcase_40 AC 76 ms
12,896 KB
testcase_41 AC 78 ms
12,772 KB
testcase_42 AC 77 ms
12,896 KB
testcase_43 AC 76 ms
12,800 KB
testcase_44 AC 3 ms
5,760 KB
testcase_45 AC 4 ms
5,888 KB
testcase_46 AC 88 ms
12,844 KB
testcase_47 AC 90 ms
12,896 KB
testcase_48 AC 4 ms
5,888 KB
testcase_49 AC 4 ms
5,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")	
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll inf = 4e18;
struct LiChao {
	struct Node {
		int l, r; ll a, b, mn, aa, bb;
		Node() { l = 0; r = 0; a = 0; b = inf; mn = inf; aa = 0; bb = 0; }
	};
	vector<Node> seg;
	ll _l, _r;
	LiChao(ll l, ll r) {
		seg.resize(2);
		_l = l; _r = r;
	}
	void propagate(int n, ll l, ll r) {
		if (seg[n].aa || seg[n].bb) {
			if (l != r) {
				if (seg[n].l == 0) seg[n].l = seg.size(), seg.push_back(Node());
				if (seg[n].r == 0) seg[n].r = seg.size(), seg.push_back(Node());
				seg[seg[n].l].aa += seg[n].aa, seg[seg[n].l].bb += seg[n].bb;
				seg[seg[n].r].aa += seg[n].aa, seg[seg[n].r].bb += seg[n].bb;
			}
			seg[n].mn += seg[n].bb;
			seg[n].a += seg[n].aa, seg[n].b += seg[n].bb;
			seg[n].aa = seg[n].bb = 0;
		}
	}
	void insert(ll L, ll R, ll a, ll b, int n, ll l, ll r) {
		if (r < L || R < l || L > R) return;
		if (seg[n].l == 0) seg[n].l = seg.size(), seg.push_back(Node());
		if (seg[n].r == 0) seg[n].r = seg.size(), seg.push_back(Node());
		propagate(n, l, r);
		seg[n].mn = min({ seg[n].mn, a * max(l,L) + b, a * min(r,R) + b });
		ll m = (l + r) >> 1;
		if (l < L || R < r) {
			if (L <= m) insert(L, R, a, b, seg[n].l, l, m);
			if (m + 1 <= R) insert(L, R, a, b, seg[n].r, m + 1, r);
			return;
		}
		ll& sa = seg[n].a, & sb = seg[n].b;
		if (a * l + b < sa * l + sb) swap(a, sa), swap(b, sb);
		if (a * r + b >= sa * r + sb) return;
		if (a * m + b < sa * m + sb) {
			swap(a, sa), swap(b, sb);
			insert(L, R, a, b, seg[n].l, l, m);
		}
		else insert(L, R, a, b, seg[n].r, m + 1, r);
	}
	void add(ll L, ll R, ll a, ll b, int n, ll l, ll r) {
		if (r < L || R < l || L > R) return;
		if (seg[n].l == 0) seg[n].l = seg.size(), seg.push_back(Node());
		if (seg[n].r == 0) seg[n].r = seg.size(), seg.push_back(Node());
		propagate(n, l, r);
		ll m = (l + r) >> 1;
		if (l < L || R < r) {
			insert(l, m, seg[n].a, seg[n].b, seg[n].l, l, m);
			insert(m + 1, r, seg[n].a, seg[n].b, seg[n].r, m + 1, r);
			seg[n].a = 0, seg[n].b = inf, seg[n].mn = inf;
			if (L <= m) add(L, R, a, b, seg[n].l, l, m);
			if (m + 1 <= R) add(L, R, a, b, seg[n].r, m + 1, r);
			seg[n].mn = min(seg[seg[n].l].mn, seg[seg[n].r].mn);
			return;
		}
		seg[n].aa += a, seg[n].bb += b;
		propagate(n, l, r);
	}
	ll get(ll x, int n, ll l, ll r) {
		if (n == 0) return inf;
		propagate(n, l, r);
		ll ret = seg[n].a * x + seg[n].b, m = (l + r) >> 1;
		if (x <= m) return min(ret, get(x, seg[n].l, l, m));
		return min(ret, get(x, seg[n].r, m + 1, r));
	}
	ll get(ll L, ll R, int n, ll l, ll r) {
		if (n == 0) return inf;
		if (r < L || R < l || L > R) return inf;
		propagate(n, l, r);
		if (L <= l && r <= R) return seg[n].mn;
		ll m = (l + r) >> 1;
		return min({ seg[n].a * max(l,L) + seg[n].b, seg[n].a * min(r,R) + seg[n].b, get(L, R, seg[n].l, l, m), get(L, R, seg[n].r, m + 1, r) });
	}
	void insert(ll L, ll R, ll a, ll b) {
		insert(L, R, a, b, 1, _l, _r);
	}
	void add(ll L, ll R, ll a, ll b) {
		add(L, R, a, b, 1, _l, _r);
	}
	ll get(ll x) {
		return get(x, 1, _l, _r);
	}
	ll get(ll L, ll R) {
		return get(L, R, 1, _l, _r);
	}
};

long long int dp[300005];
long long int a[300005];
long long int x[300005];
long long int y[300005];
int n;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n;

	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];
	fill(dp, dp + 300005, 1e18);
	dp[0] = 0;	

	//dp[i] = min(0<=j<i) dp[j] + a[i]^2 - 2*x[j+1]*a[i] + x[j+1]^2 + y[j+1]^2
	// A[i] = -2*x[i] , B[j] = a[j+1] , C[j] = dp[j] + x[j+1]^2 + y[j+1]^2, D[i] = a[i]^2

	LiChao tree(-1e12, 1e12);
	tree.insert(-1e12,1e12,x[1],dp[0] + x[1]*x[1] + y[1]*y[1]);
	for (int i = 1; i <= n; i++)
	{
		//cout << cht.query2(B*i) + (B * ((i * (i + 1)) / 2)) - (A * i) << '\n';
		dp[i] = tree.get(-2*a[i]) + a[i]*a[i];
		tree.insert(-1e12,1e12,x[i+1],dp[i] + x[i+1]*x[i+1] + y[i+1]*y[i+1]);
	}

	cout << dp[n] << '\n';

	return 0;
}
0