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

提出ソース

結果

問題	No.703 ゴミ拾い Easy
ユーザー	snrnsidy
提出日時	2023-04-17 13:08:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,886 bytes
コンパイル時間	3,929 ms
コンパイル使用メモリ	368,028 KB
実行使用メモリ	13,056 KB
最終ジャッジ日時	2024-10-12 14:21:07
合計ジャッジ時間	9,970 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 5,632 KB
testcase_01	AC	5 ms 5,760 KB
testcase_02	AC	5 ms 5,760 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	5 ms 5,760 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	74 ms 12,768 KB
testcase_37	AC	78 ms 12,768 KB
testcase_38	AC	75 ms 12,800 KB
testcase_39	AC	74 ms 12,764 KB
testcase_40	AC	75 ms 12,672 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	AC	4 ms 5,632 KB
testcase_45	AC	4 ms 5,760 KB
testcase_46	AC	86 ms 12,800 KB
testcase_47	AC	87 ms 12,800 KB
testcase_48	WA	-
testcase_49	WA	-

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

ソースコード

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[j+1]^2 - 2*a[j+1]*x[i] + x[i]^2 + y[i]^2
	// A[i] = -2*x[i] , B[j] = a[j+1] , C[j] = dp[j] + a[j+1]^2, D[i] = x[i]^2 + y[i]^2

	LiChao tree(-1e12, 1e12);
	tree.insert(-1e12,1e12,a[1],dp[0] + a[1]*a[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*x[i]) + x[i]*x[i] + y[i]*y[i];
		tree.insert(-1e12,1e12,a[i+1],dp[i] + a[i+1]*a[i+1]);
	}

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

	return 0;
}

yukicoder

結果

テストケース

ソースコード