Submission #291176

#	Time	Username	Problem	Language	Result	Execution time	Memory
291176		Bench0310	Building Bridges (CEOI17_building)	C++17	100 / 100	82 ms	9848 KiB

building

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf=(1ll<<60);

struct line
{
    ll k,n;
    mutable ll r;
    line(ll a,ll b,ll c){k=a;n=b;r=c;}
    bool operator<(const line &o)const{return k>o.k;}
    bool operator<(const ll &o)const{return r<o;}
};

struct cht
{
    set<line,less<>> s;
    ld intersect(line a,line b){return (((ld)b.n-a.n)/(a.k-b.k));}
    void upd(set<line>::iterator it,ll nr){it->r=nr;}
    void add(ll k,ll n)
    {
        line now(k,n,0);
        auto it=s.lower_bound(now);
        if(it!=s.end()&&it->k==k)
        {
            if(it->n>n) it=s.erase(it);
            else return;
        }
        if(it!=s.end()&&it!=s.begin()&&intersect(*prev(it),now)>intersect(now,*it)) return;
        s.insert(now);
        while(it!=s.end()&&next(it)!=s.end()&&intersect(now,*it)>intersect(*it,*next(it))) it=s.erase(it);
        it--;
        while(it!=s.begin()&&prev(it)!=s.begin()&&intersect(now,*prev(it))<intersect(*prev(it),*prev(prev(it)))) s.erase(prev(it));
        if(it!=s.begin()) upd(prev(it),floor(intersect(*prev(it),*it)));
        if(next(it)!=s.end()) upd(it,floor(intersect(*it,*next(it))));
        else upd(it,inf);
    }
    ll query(ll a)
    {
        line best=*s.lower_bound(a);
        return (best.k*a+best.n);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> h(n+1,0);
    for(int i=1;i<=n;i++) cin >> h[i];
    vector<ll> w(n+1,0);
    for(int i=1;i<=n;i++) cin >> w[i];
    vector<ll> sum(n+1,0);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
    cht c;
    c.add(-2*h[1],h[1]*h[1]-w[1]);
    for(int i=2;i<=n;i++)
    {
        ll dp=h[i]*h[i]+sum[i-1]+c.query(h[i]);
        c.add(-2*h[i],dp+h[i]*h[i]-sum[i]);
        if(i==n) cout << dp << "\n";
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40