Submission #1205382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205382		hahahoang132	Building Bridges (CEOI17_building)	C++20	100 / 100	254 ms	12164 KiB

building

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 1e6 + 6;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;


struct line
{
    ll t;
    ld x;
    ll a,b;
};

bool operator < (line t1, line t2)
{
    if(t1.t || t2.t) return t1.x < t2.x;
    else return t1.a > t2.a;
}

struct lc
{
    set<line> s;
    line prev(line a)
    {
        if(s.lower_bound(a) == s.begin()) return {-1,0,0,0};
        else return *(--s.lower_bound(a));
    }
    line next(line a)
    {
        if(s.upper_bound(a) == s.end())  return {-1,0,0,0};
        else return *(s.upper_bound(a));
    }
    void calx(line a)
    {
        line pa = prev(a);
        if(pa.t == -1) return;
        s.erase(a);
        a.x = giao(pa,a);
        s.insert(a);
    }
    ld giao(line a, line b)
    {
        return (ld)(a.b - b.b) / (b.a - a.a);
    }
    ll bad(line a)
    {
        line pa = prev(a);
        line na = next(a);
        if(pa.t == -1 || na.t == -1) return 0;
        return (giao(pa,a) >= giao(pa,na));
    }
    void add(ll a, ll b)
    {
        line it;
        if(s.lower_bound({0,0,a,b}) != s.end())
        {
            it = *s.lower_bound({0,0,a,b});
            if(it.a == a)
            {
                if(it.b <= b) return;
                s.erase(it);
            }
        }
        it = {0,0,a,b};
        s.insert(it);
        if(bad(it)) s.erase(it);
        else
        {
            while(true)
            {
                line pre = prev(it);
                if(pre.t == -1) break;
                if(bad(pre)) s.erase(pre);
                else break;
            }
            while(true)
            {
                line nex = next(it);
                if(nex.t == -1) break;
                if(bad(nex)) s.erase(nex);
                else break;
            }
            calx(it);
            if(next(it).t != -1) calx(next(it));
        }
    }
    ll get(ll x)
    {
        line ans = *(--s.upper_bound({1,(ld)x,0,0}));
        return ans.a * x + ans.b;
    }
};
lc f;
ll h[N],w[N],d[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >>n;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        cin >> h[i];
    }
    ll sum = 0;
    for(i  = 1;i <= n;i++)
    {
        cin >> w[i];
        sum += w[i];
    }
    d[1] = -w[1];
    for(i = 2;i <= n;i++)
    {
        f.add(-2 * h[i - 1], d[i - 1] + h[i - 1] * h[i - 1]);
        d[i] = f.get(h[i]) - w[i] + h[i] * h[i];
    }
    cout << sum + d[n];
}

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