結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-19 16:09:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 164 ms / 1,500 ms
コード長 1,542 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 195,088 KB
実行使用メモリ 37,648 KB
最終ジャッジ日時 2025-03-19 16:09:16
合計ジャッジ時間 7,833 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~
main.cpp:72:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |         for(int i=1;i<=n;i++) scanf("%d",&x[i]);
      |                               ~~~~~^~~~~~~~~~~~
main.cpp:73:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |         for(int i=1;i<=n;i++) scanf("%d",&y[i]);
      |                               ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const long long inf=1e18;
int a[N];
int x[N];
int y[N];
long long dp[N];
struct node
{
	long long k,b;
	int l,r;
	long long gety(long long x){return k*x+b;}
}tr[N<<2];
void build(int id,int l,int r)
{
	tr[id]={0,inf,l,r};
	if(l==r) return;
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
}
void change(int id,node p)
{
	int l=tr[id].l,r=tr[id].r;
	int mid=(l+r)>>1;
	if(p.l<=l&&r<=p.r)
	{
		if(p.gety(l)<tr[id].gety(l)&&p.gety(r)<tr[id].gety(r))
		{
			tr[id].k=p.k;
			tr[id].b=p.b;
		}
		if(tr[id].l==tr[id].r) return;
		if(p.gety(mid)<tr[id].gety(mid))
		{
			swap(tr[id].k,p.k);
			swap(tr[id].b,p.b);
		}
		if(p.gety(l)<tr[id].gety(l))
		{
			change(id<<1,p);
		}
		if(p.gety(r)<tr[id].gety(r))
		{
			change(id<<1|1,p);
		}
	}
	else
	{
		if(p.l<=mid) change(id<<1,p);
		if(p.r>mid) change(id<<1|1,p); 
	}
}
long long query(int id,int x)
{
	if(tr[id].l==tr[id].r) return tr[id].gety(x);
	int mid=(tr[id].l+tr[id].r)>>1;
	long long ans=tr[id].gety(x);
	if(x<=mid) return min(ans,query(id<<1,x));
	else return min(ans,query(id<<1|1,x));
}
int main()
{
	int n;
	cin>>n;
	build(1,-200000,200000);
	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]);
	change(1,{x[1],1LL*y[1]*y[1]+1LL*x[1]*x[1],-200000,200000});
	for(int i=1;i<=n;i++)
	{
		dp[i]=1LL*a[i]*a[i]+query(1,-2LL*a[i]);
		change(1,{x[i+1],1LL*y[i+1]*y[i+1]+1LL*x[i+1]*x[i+1]+dp[i],-200000,200000});
	}
	cout<<dp[n];
 }
0