結果

問題 No.705 ゴミ拾い Hard
ユーザー vjudge1
提出日時 2025-03-21 17:38:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 134 ms / 1,500 ms
コード長 2,422 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 29,568 KB
実行使用メモリ 13,956 KB
最終ジャッジ日時 2025-03-21 17:38:44
合計ジャッジ時間 5,895 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:69:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |                 scanf("%d", a + i);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:73:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |                 scanf("%d", x + i);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:75:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |                 scanf("%d", y + i);
      |                 ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
int n, a[300005], x[300005], y[300005];
long long dp[300005];
namespace segmentTree
{
	int val[400005];
	long long k[400005], b[400005];
	inline int lson(int x) { return x << 1; }
	inline int rson(int x) { return x << 1 | 1; }
	inline long long abs(long long x) { return x < 0 ? -x : x; }
	inline long long function(long long k, long long b, long long x) { return abs(x - k) * abs(x - k) * abs(x - k) + b; }
	inline long long min(long long x, long long y) { return x < y ? x : y; }
	void build(int root, int tl, int tr)
	{
		k[root] = 1000000;
		b[root] = 1e18;
		if (tl != tr)
		{
			int tm = (tl + tr) >> 1;
			build(lson(root), tl, tm);
			build(rson(root), tm + 1, tr);
		}
	}
	void update(int newk, long long newb, int root, int tl, int tr)
	{
		bool lbetter = function(k[root], b[root], tl) > function(newk, newb, tl);
		bool rbetter = function(k[root], b[root], tr) > function(newk, newb, tr);
		if (lbetter && rbetter)
		{
			k[root] = newk;
			b[root] = newb;
			return;
		}
		if (!lbetter && !rbetter)
			return;
		int tm = (tl + tr) >> 1;
		bool mlbetter = function(k[root], b[root], tm) > function(newk, newb, tm);
		if (lbetter && mlbetter)
		{
			k[root] ^= newk ^= k[root] ^= newk;
			b[root] ^= newb ^= b[root] ^= newb;
			return update(newk, newb, rson(root), tm + 1, tr);
		}
		bool mrbetter = function(k[root], b[root], tm + 1) > function(newk, newb, tm + 1);
		if (rbetter && mrbetter)
		{
			k[root] ^= newk ^= k[root] ^= newk;
			b[root] ^= newb ^= b[root] ^= newb;
			return update(newk, newb, lson(root), tl, tm);
		}
		if (lbetter)
			update(newk, newb, lson(root), tl, tm);
		else
			update(newk, newb, rson(root), tm + 1, tr);
	}
	long long query(int i, int root, int tl, int tr)
	{
		if (i < tl || tr < i)
			return 2e18;
		long long res = function(k[root], b[root], i);
		if (tl == tr)
			return res;
		int tm = (tl + tr) >> 1;
		return min(res, i <= tm ? query(i, lson(root), tl, tm) : query(i, rson(root), tm + 1, tr));
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i);
	for (int i = 1; i <= n; ++i)
		scanf("%d", x + i);
	for (int i = 1; i <= n; ++i)
		scanf("%d", y + i);
	segmentTree::build(1, 0, 100000);
	for (int i = 1; i <= n; ++i)
	{
		segmentTree::update(x[i], dp[i - 1] + y[i] * (long long)(y[i]) * (long long)(y[i]), 1, 0, 100000);
		dp[i] = segmentTree::query(a[i], 1, 0, 100000);
	}
	printf("%lld\n", dp[n]);
	return 0;
}
0