Submission #1237975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237975		chikien2009	Building Bridges (CEOI17_building)	C++20	100 / 100	36 ms	5188 KiB

building

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct LINE
{
    long long a = 2e9, b = 1e18;
    inline long long Val(long long x)
    {
        return a * x + b;
    }
};

struct LICHAO_TREE
{
    LINE tree[5000000];
    inline void Add(int ind, int l, int r, LINE v)
    {
        int m = (l + r) >> 1;
        if (tree[ind].Val(m) > v.Val(m))
        {
            swap(tree[ind], v);
        }
        if (l < r)
        {
            if (tree[ind].Val(l) > v.Val(l))
            {
                Add(ind << 1, l, m, v);
            }
            if (tree[ind].Val(r) > v.Val(r))
            {
                Add(ind << 1 | 1, m + 1, r, v);
            }
        }
    }
    inline long long Get(int ind, int l, int r, int x)
    {
        if (l == r)
        {
            return tree[ind].Val(x);
        }
        int m = (l + r) >> 1;
        if (x <= m)
        {
            return min(tree[ind].Val(x), Get(ind << 1, l, m, x));
        }
        return min(tree[ind].Val(x), Get(ind << 1 | 1, m + 1, r, x));
    }
} lichao;

int n;
long long pre, f, h[100000], w[100000];

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> h[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> w[i];
    }
    for (int i = 0; i < n; ++i)
    {
        f = (i != 0) * (lichao.Get(1, 0, 1e6, h[i]) + pre + h[i] * h[i]);
        pre += w[i];
        lichao.Add(1, 0, 1e6, {-2 * h[i], f - pre + h[i] * h[i]});
    }
    cout << f;
    return 0;
}

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