#860425 (C++17) No.703 ゴミ拾い Easy

提出ソース

結果

問題	No.703 ゴミ拾い Easy
ユーザー	snrnsidy
提出日時	2023-04-17 13:11:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	131 ms / 1,500 ms
コード長	5,906 bytes
コンパイル時間	3,977 ms
コンパイル使用メモリ	366,008 KB
実行使用メモリ	13,152 KB
最終ジャッジ日時	2024-04-20 18:24:05
合計ジャッジ時間	8,048 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 10,592 KB
testcase_01	AC	3 ms 10,332 KB
testcase_02	AC	2 ms 10,332 KB
testcase_03	AC	3 ms 10,972 KB
testcase_04	AC	3 ms 10,464 KB
testcase_05	AC	3 ms 10,720 KB
testcase_06	AC	3 ms 10,464 KB
testcase_07	AC	3 ms 10,972 KB
testcase_08	AC	3 ms 10,464 KB
testcase_09	AC	2 ms 10,204 KB
testcase_10	AC	4 ms 10,460 KB
testcase_11	AC	3 ms 10,460 KB
testcase_12	AC	3 ms 9,948 KB
testcase_13	AC	4 ms 11,228 KB
testcase_14	AC	4 ms 11,112 KB
testcase_15	AC	3 ms 10,212 KB
testcase_16	AC	4 ms 10,984 KB
testcase_17	AC	4 ms 10,472 KB
testcase_18	AC	4 ms 10,732 KB
testcase_19	AC	3 ms 10,212 KB
testcase_20	AC	3 ms 10,216 KB
testcase_21	AC	4 ms 11,240 KB
testcase_22	AC	4 ms 10,476 KB
testcase_23	AC	4 ms 10,980 KB
testcase_24	AC	130 ms 13,024 KB
testcase_25	AC	131 ms 13,024 KB
testcase_26	AC	130 ms 13,152 KB
testcase_27	AC	130 ms 13,028 KB
testcase_28	AC	126 ms 12,892 KB
testcase_29	AC	128 ms 13,024 KB
testcase_30	AC	128 ms 13,028 KB
testcase_31	AC	128 ms 13,104 KB
testcase_32	AC	130 ms 13,148 KB
testcase_33	AC	130 ms 13,020 KB
testcase_34	AC	76 ms 12,880 KB
testcase_35	AC	75 ms 13,024 KB
testcase_36	AC	76 ms 12,908 KB
testcase_37	AC	75 ms 12,896 KB
testcase_38	AC	76 ms 12,900 KB
testcase_39	AC	76 ms 12,896 KB
testcase_40	AC	75 ms 12,896 KB
testcase_41	AC	77 ms 12,976 KB
testcase_42	AC	75 ms 12,892 KB
testcase_43	AC	75 ms 12,900 KB
testcase_44	AC	3 ms 10,844 KB
testcase_45	AC	3 ms 9,948 KB
testcase_46	AC	90 ms 12,896 KB
testcase_47	AC	93 ms 12,892 KB
testcase_48	AC	4 ms 10,088 KB
testcase_49	AC	4 ms 10,476 KB

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード