Submission #1332695

#TimeUsernameProblemLanguageResultExecution timeMemory
1332695fatuu27Building Bridges (CEOI17_building)C++20
30 / 100
19 ms2792 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <climits>

using namespace std;
using ll = long long;
const ll inf = LLONG_MAX;
int n;
vector<int> H,W;
vector<ll> dp,sp;
struct Line
{
    ll m,k;
    mutable ll x;
    bool operator<(const Line &other) const
    {
        return m>other.m;///pante descrescatoare pt minim
    }
    bool operator<(ll other) const
    {
        return x<other;
    }
    ll operator()(ll x) const
    {
        return m*x+k;
    }
};
struct CHT : multiset<Line,less<>>
{
    ll div(ll a,ll b)
    {
        return a/b-((a%b) && ((a^b)<0));
    }
    bool isect(iterator a,iterator b)
    {
        if(b==end())
        {
            ///practic a ii ultima linie deci se intersecteaza f departe
            a->x=inf;
            return 0;
        }
        if(a->m==b->m)
        {
            if(a->k<b->k)
                a->x=inf;
            else
                a->x=-inf;
        }
        else
        {
            a->x=div(b->k-a->k,a->m-b->m);
        }
        return a->x>=b->x; ///daca e adv sterg b
    }
    void add(ll m,ll k)
    {
        auto c=insert({m,k,0}),b=c++,a=b;
        while(isect(b,c))
            c=erase(c);
        if(a!=begin() && isect(--a,b))
            isect(a,b=erase(b));
        while((b=a)!=begin() && (--a)->x>=b->x)
            isect(a,erase(b));
    }
    ll query(ll x)
    {
        Line line=*lower_bound(x);
        return line(x);
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    H=W=vector<int>(n+1);
    dp=sp=vector<ll>(n+1);
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=1;i<=n;i++)
        cin>>W[i],sp[i]=sp[i-1]+W[i];
    for(int i=1;i<=n;i++)
        dp[i]=inf;
    dp[1]=0;
    CHT hull;
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            hull.add(-2*H[i],H[i]*H[i]-sp[i]+dp[i]);
            continue;
        }
        dp[i]=hull.query(H[i])+sp[i-1]+H[i]*H[i];
        hull.add(-2*H[i],H[i]*H[i]-sp[i]+dp[i]);
    }
    cout<<dp[n];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...