結果

問題 No.703 ゴミ拾い Easy
ユーザー beet
提出日時 2018-06-15 23:27:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 326 ms / 1,500 ms
コード長 2,342 bytes
コンパイル時間 2,064 ms
コンパイル使用メモリ 169,472 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2025-01-02 13:52:54
合計ジャッジ時間 10,271 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<typename T,T INF,bool isMin>
struct DynamicConvexHullTrick {
  using number = double;
  struct Line {
    T m,b,val;
    number x;
    bool q;
    Line(T m=0,T b=0):m(m),b(b),val(0),x(-INF),q(false){}
    
    T eval(T x) const{return m*x+b;}
    bool parallel(const Line &l) const{return m==l.m;}
    number intersect(const Line &l) const{
      return parallel(l)?number(INF):number(l.b-b)/number(m-l.m);
    }
    bool operator<(const Line &l) const{
      if(l.q) return x<l.val;
      return m<l.m;
    }
  };
  
  set<Line> hull;
  using iter = typename set<Line>::iterator;

  bool cPrev(iter it){return it!=hull.begin();}
  bool cNext(iter it){return it!=hull.end()&&next(it)!=hull.end();}

  bool bad(const Line &l1,const Line &l2,const Line &l3){
    return l1.intersect(l3) <= l1.intersect(l2);
  }
  bool bad(iter it){
    return cPrev(it)&&cNext(it)&&bad(*prev(it),*it,*next(it));
  }

  iter update(iter it){
    if(!cPrev(it)) return it;
    number x=it->intersect(*prev(it));
    Line tmp(*it);
    tmp.x=x;
    it=hull.erase(it);
    return hull.insert(it,tmp);
  }
  
  void addLine(T m,T b){
    if(isMin) m=-m,b=-b;
    Line l(m,b);
    iter it=hull.lower_bound(l);
    if(it!=hull.end()&&l.parallel(*it)){
      if(it->b<b) it=hull.erase(it);
      else return;
    }
    it=hull.insert(it,l);
    if(bad(it)){
      hull.erase(it);
      return;
    }
    while(cPrev(it)&&bad(prev(it))) hull.erase(prev(it));
    while(cNext(it)&&bad(next(it))) hull.erase(next(it));

    it=update(it);
    if(cPrev(it)) update(prev(it));
    if(cNext(it)) update(next(it));
  }

  T query(T x){
    if(hull.empty()){
      if(isMin) return INF;
      return -INF;
    }
    Line q;
    q.val=x;q.q=1;
    iter it=--hull.lower_bound(q);
    if(isMin) return -(it->eval(x));
    return it->eval(x);
  }
  
} ;

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n),x(n),y(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  for(Int i=0;i<n;i++) cin>>x[i];
  for(Int i=0;i<n;i++) cin>>y[i];

  const Int INF = 1e18;
  vector<Int> dp(n+1,INF);
  dp[0]=0;

  DynamicConvexHullTrick<Int, INF, true> dc;
  for(Int i=0;i<n;i++){
    dc.addLine(-2*x[i],dp[i]+x[i]*x[i]+y[i]*y[i]);
    dp[i+1]=dc.query(a[i])+a[i]*a[i];
  }
  cout<<dp[n]<<endl;
  return 0;
}
0