test/yuki1948.test.cpp

View this file on GitHub
Last update: 2023-04-05 23:10:22+09:00
Problem: https://yukicoder.me/problems/1948

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/1948"

#include "../template.hpp"

#include "../DataStructure/LiChaoTree.hpp"

signed main(){
    int n;cin>>n;
    vector<ll> a(n),x(n),y(n);
    cin>>a>>x>>y;


    vector<ll> dp(n+1,0);
    dp[0]=0;

    LiChaoTree<ll> seg(a,LINF);
    seg.add(-2*x[0],dp[0]+x[0]*x[0]+y[0]*y[0]);

    rep(i,n){
        dp[i+1]=seg.query(a[i])+a[i]*a[i];
        if(i<n-1)seg.add(-2*x[i+1],dp[i+1]+x[i+1]*x[i+1]+y[i+1]*y[i+1]);
    }
    cout<<dp[n]<<endl;
    return 0;
}

#line 1 "test/yuki1948.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/1948"

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/yuki1948.test.cpp"

#line 1 "DataStructure/LiChaoTree.hpp"
// min
template<typename T>
struct LiChaoTree{
    private:
    struct Line{
        T a,b;
        Line(T a,T b):a(a),b(b){}
        T operator()(T x){return a*x+b;}
    };
    
    void add(Line &li,int k,int l,int r){
        int m=(l+r)/2;
        // replace flag
        bool cl=li(xs[l])<seg[k](xs[l]),cm=li(xs[m])<seg[k](xs[m]);
        if(cm) swap(seg[k],li);// ! みてる区間においてみてる直線を切り替える
        if(l+1>=r) return ;
        // どちらかにしか降りないので計算量がlog
        if(cl!=cm) add(li,2*k,l,m);
        else add(li,2*k+1,m,r);
        return ;
    }

    vector<T> xs;
    vector<Line> seg;
    int sz;

    public:
    LiChaoTree(const vector<T> &x,T TINF):xs(x){
        sort(begin(xs),end(xs));
        xs.erase(unique(begin(xs),end(xs)),end(xs));
        sz=1;
        while(sz<(int)xs.size()) sz<<=1;
        while((int)xs.size()<sz) xs.push_back(xs.back()+1);
        seg.assign(2*sz,Line(0,TINF));
    }

    // add ax+b
    void add(T a,T b){
        Line l(a,b);
        add(l,1,0,sz);
    }

    T query(T val){
        int k=lower_bound(begin(xs),end(xs),val)-begin(xs);
        assert(xs[k]==val);
        k+=sz;
        T ret=seg[k](val);
        for(;k;k>>=1) ret=min(ret,seg[k](val));
        return ret;
    }
};
#line 6 "test/yuki1948.test.cpp"

signed main(){
    int n;cin>>n;
    vector<ll> a(n),x(n),y(n);
    cin>>a>>x>>y;


    vector<ll> dp(n+1,0);
    dp[0]=0;

    LiChaoTree<ll> seg(a,LINF);
    seg.add(-2*x[0],dp[0]+x[0]*x[0]+y[0]*y[0]);

    rep(i,n){
        dp[i+1]=seg.query(a[i])+a[i]*a[i];
        if(i<n-1)seg.add(-2*x[i+1],dp[i+1]+x[i+1]*x[i+1]+y[i+1]*y[i+1]);
    }
    cout<<dp[n]<<endl;
    return 0;
}