結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-21 17:48:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 129 ms / 1,500 ms
コード長 1,999 bytes
コンパイル時間 1,662 ms
コンパイル使用メモリ 162,988 KB
実行使用メモリ 59,904 KB
最終ジャッジ日時 2025-03-21 17:48:47
合計ジャッジ時間 6,908 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define N 300005
#define int long long
#define Eps 1e-6
using namespace std;
struct line{
    int k,b;
    bool flag;int ls,rs;
    line(){
    	ls=rs=0;
	}
    int get(const int x)const{
        return k*x+b;
    }
    double getIntersectionX(const line &x)const{
        return (b-x.b)/1.0/(x.k-k);
    }
};
struct LiChaoTree{
    line Tree[N<<2];
    int Root,Ncnt;
    inline void Add(int &id,int L,int R,line p){
    	if(!id){
    		id=++Ncnt;
		}
        if(!Tree[id].flag){
            Tree[id].k=p.k;Tree[id].b=p.b;
            Tree[id].flag=1;
        }else if(p.get(L)<Tree[id].get(L)&&p.get(R)<Tree[id].get(R)){
            Tree[id].k=p.k;Tree[id].b=p.b;
        }else if(p.get(L)<Tree[id].get(L)||p.get(R)<Tree[id].get(R)){
            int mid=L+R>>1;
            if(p.get(mid)<Tree[id].get(mid)){
                swap(p.b,Tree[id].b);swap(p.k,Tree[id].k);
            }
            if((double)(mid)-p.getIntersectionX(Tree[id])>Eps){
                Add(Tree[id].ls,L,mid,p);
            }else{
                Add(Tree[id].rs,mid+1,R,p);
            }
        }
    }
    inline int Query(int id,int L,int R,int val){
    	if(!id){
    		return 1e18;
		}
		if(!Tree[id].flag){
			return 1e18;
		}
        if(L==R){
        	if(!Tree[id].flag){
        		return 1e18;
			}
            return Tree[id].get(val);
        }int mid=L+R>>1;
        int Ans=Tree[id].get(val);
        if(val<=mid){
            return min(Ans,Query(Tree[id].ls,L,mid,val));
        }else{
            return min(Ans,Query(Tree[id].rs,mid+1,R,val));
        }
    }
}LCTree;
int n,dp[N],x[N],y[N],a[N];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	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];
	}
	for(int i=1;i<=n;i++){
		line p;p.b=dp[i-1]+y[i]*y[i]+x[i]*x[i];p.k=-2*x[i]; 
		LCTree.Add(LCTree.Root,1,20000000,p);
		dp[i]=a[i]*a[i]+LCTree.Query(1,1,20000000,a[i]);
		
	}cout<<dp[n];
}
0