Submission #1326351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326351		fatuu27	Building Bridges (CEOI17_building)	C++20	0 / 100	19 ms	2184 KiB

building

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <climits>
using ll = long long;
using namespace std;
const ll inf = LLONG_MAX;
struct Line
{
    ll m,k;
    mutable ll x;
    bool ismin;
    Line(ll m,ll k,ll x, bool ismin) : m(m),k(k),ismin(ismin) {}
    bool operator<(const Line &l) const
    {
        if(ismin==false)
            return m<l.m;
        else
            return m>l.m;
    }
    bool operator<(ll x2) const
    {
        return x<x2;
    }
};
template<bool ismin>
struct CHT : multiset<Line,less<>>
{
    /// suporta add, query
    ll div(ll a,ll b)
    {///floor division
        if(a%b && a^b<0)
            return a/b-1;
        return a/b;
    }
    bool isect(iterator a,iterator b)
    {
        if(b==end())
        {
            a->x=inf;
            return false;
        }
        if(a->m==b->m)
        {
            if(a->k<b->k)
                a->x=ismin ? inf : -inf;
            else
                a->x=ismin ? -inf : inf;
        }
        else
            a->x=div(b->k-a->k,a->m-b->m);
        return a->x>=b->x;
    }
    void add(ll m,ll k)
    {
        auto c=emplace(m,k,0,ismin),b=c++,a=b;
        while(isect(b,c)) ///elimin la dreapta si c tot merge in dreapta
            c=erase(c);
        if(a!=begin() && isect(--a,b)) ///poate o elimin fix pe ea
            isect(a,b=erase(b));
        while((b=a)!=begin() && (--a)->x>=b->x) ///elimin din stanga
            isect(a,erase(b));
    }
    ll query(ll x)
    {
        auto line=*lower_bound(x);
        return line.m*x+line.k;
    }
};
int n,H[100005];
ll W[100005],dp[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=1;i<=n;i++)
        cin>>W[i],W[i]+=W[i-1];
    CHT<true> hull;
    for(int i=1;i<=n;i++)
    {
        if(i>=2)
            dp[i]=hull.query(H[i])+H[i]*H[i]+W[i-1];
        hull.add(-2*H[i],dp[i]+H[i]*H[i]-W[i]);
    }
    cout<<dp[n];
    return 0;
}

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