Submission #1020666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020666		NValchanov	Building Bridges (CEOI17_building)	C++17	100 / 100	118 ms	67192 KiB

building

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN = 1e5 + 10;
const ll MAXH = 1e6 + 10;
const ll MAXW = 1e6 + 10;
const ll INF = 4e18 + 10;

ll n;
ll w[MAXN];
ll h[MAXN];
ll prefw[MAXN];
ll dp[MAXN];

struct lichao
{
    struct line
    {
        ll a, b;
        line()
        {
            a = 0;
            b = 0;
        }
        line(ll _a, ll _b)
        {
            a = _a;
            b = _b;
        }
        ll get_val(ll x)
        {
            return a * x + b;
        }
    };

    line tree[4 * MAXH];

    void build(ll left, ll right, ll idx)
    {
        tree[idx] = {0, INF};

        if(left == right)
            return;

        ll mid = left + (right - left) / 2;
        build(left, mid, 2 * idx);
        build(mid + 1, right, 2 * idx + 1);
    }

    void insert(ll left, ll right, ll idx, line l)
    {
        if(left == right)
        {
            if(l.get_val(left) < tree[idx].get_val(left))
                tree[idx] = l;

            return;
        }

        ll mid = left + (right - left) / 2;
        if(tree[idx].a < l.a)
            swap(tree[idx], l);

        if(tree[idx].get_val(mid) > l.get_val(mid))
        {
            swap(tree[idx], l);
            insert(left, mid, 2 * idx, l);
        }
        else insert(mid + 1, right, 2 * idx + 1, l);
    }

    ll query(ll left, ll right, ll idx, ll x)
    {
        if(left == right)
            return tree[idx].get_val(x);

        ll mid = left + (right - left) / 2;

        if(x < mid)
            return min(tree[idx].get_val(x), query(left, mid, 2 * idx, x));
        
        return min(tree[idx].get_val(x), query(mid + 1, right, 2 * idx + 1, x));
    }

    void build()
    {
        build(1, MAXH, 1);
    }

    void insert(ll a, ll b)
    {
        insert(1, MAXH, 1, line(a, b));
    }

    ll query(ll x)
    {
        return query(1, MAXH, 1, x);
    }
};

lichao li;

void read()
{
    cin >> n;
    for(ll i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for(ll i = 1; i <= n; i++)
    {
        cin >> w[i];
        prefw[i] = prefw[i - 1] + w[i];
    }
}

void solve()
{
    li.build();

    dp[1] = 0;
    li.insert(-2 * h[1], h[1] * h[1] + dp[1] - prefw[1]);

    for(ll i = 2; i <= n; i++)
    {
        dp[i] = li.query(h[i]) + prefw[i - 1] + h[i] * h[i];

        li.insert(-2 * h[i], h[i] * h[i] + dp[i] - prefw[i]);
    }

    cout << dp[n] << endl;
}

int main()
{
    read();
    solve();

    return 0;
}

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