結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2025-03-18 18:51:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 1,500 ms |
コード長 | 1,074 bytes |
コンパイル時間 | 1,604 ms |
コンパイル使用メモリ | 161,740 KB |
実行使用メモリ | 10,076 KB |
最終ジャッジ日時 | 2025-03-18 18:51:28 |
合計ジャッジ時間 | 8,147 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LD; const int N=3e5+5; LL dp[N]; int x[N],y[N],a[N],n,q[N],tl,hd; inline LL Y(int i){ return dp[i]+1ll*y[i+1]*y[i+1]+1ll*x[i+1]*x[i+1]; } inline LL X(int i){ return x[i+1]; } inline LD Slope(int i,int j){ return (LD)(1.0)*(Y(i)-Y(j))/(X(i)-X(j)); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 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++){ if(i!=1){ // cout<<Slope(q[hd],q[hd+1])<<"\n"; } while(hd<tl && Slope(q[hd],q[hd+1])<=2*a[i]) hd++; int j=q[hd]; dp[i]=dp[j]+1ll*(a[i]-x[j+1])*(a[i]-x[j+1])+1ll*y[j+1]*y[j+1]; //cout<<i<<"="<<dp[i]<<" frm "<<j+1<<"\n"; bool fail=false; while(hd<=tl){ if(X(q[tl])==X(i)){ if(Y(q[tl])>=Y(i)) tl--; else{ fail=true; break; } }else if(hd<tl && Slope(q[tl-1],q[tl])>=Slope(q[tl],i)) tl--; else break; } if(!fail) q[++tl]=i; } cout<<dp[n]; }