結果

問題 No.703 ゴミ拾い Easy
ユーザー beetbeet
提出日時 2018-06-15 23:27:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 292 ms / 1,500 ms
コード長 2,342 bytes
コンパイル時間 1,669 ms
コンパイル使用メモリ 174,332 KB
実行使用メモリ 12,728 KB
最終ジャッジ日時 2023-08-30 18:56:36
合計ジャッジ時間 9,652 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 3 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 3 ms
4,380 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 3 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 292 ms
12,724 KB
testcase_25 AC 291 ms
12,456 KB
testcase_26 AC 290 ms
12,456 KB
testcase_27 AC 290 ms
12,496 KB
testcase_28 AC 291 ms
12,508 KB
testcase_29 AC 290 ms
12,484 KB
testcase_30 AC 292 ms
12,604 KB
testcase_31 AC 291 ms
12,460 KB
testcase_32 AC 292 ms
12,440 KB
testcase_33 AC 290 ms
12,648 KB
testcase_34 AC 202 ms
12,348 KB
testcase_35 AC 205 ms
12,240 KB
testcase_36 AC 202 ms
12,348 KB
testcase_37 AC 202 ms
12,488 KB
testcase_38 AC 201 ms
12,420 KB
testcase_39 AC 203 ms
12,236 KB
testcase_40 AC 200 ms
12,420 KB
testcase_41 AC 201 ms
12,496 KB
testcase_42 AC 201 ms
12,728 KB
testcase_43 AC 200 ms
12,384 KB
testcase_44 AC 1 ms
4,376 KB
testcase_45 AC 1 ms
4,376 KB
testcase_46 AC 267 ms
12,484 KB
testcase_47 AC 254 ms
12,488 KB
testcase_48 AC 2 ms
4,500 KB
testcase_49 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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