제출 #753488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753488		finn__	Building Bridges (CEOI17_building)	C++17	100 / 100	80 ms	7216 KiB

building

#include <bits/stdc++.h>
using namespace std;

struct linear_fn
{
    int64_t m, t;
    linear_fn(int64_t m, int64_t t) { this->m = m, this->t = t; }
    int64_t operator()(int64_t x) const { return m * x + t; }
    bool intersects_earlier(linear_fn const &g, linear_fn const &h)
    {
        return (__int128_t)(h.t - t) * (m - g.m) <= (__int128_t)(g.t - t) * (m - h.m);
    }
};

constexpr size_t N = 100000;

int64_t h[N], w[N], f[N];

void add_function(vector<linear_fn> &hull, linear_fn const &f)
{
    while (hull.size() >= 2 && hull[hull.size() - 2].intersects_earlier(hull.back(), f))
        hull.pop_back();
    hull.push_back(f);
}

vector<linear_fn> cdq(size_t a, size_t b)
{
    if (a == b)
        return {linear_fn(-2 * h[a], f[a] + h[a] * h[a] - w[a])};
    vector<linear_fn> r = cdq(a, (a + b) / 2);
    if (!r.empty())
        for (size_t i = (a + b) / 2 + 1; i <= b; ++i)
        {
            size_t x = 0, y = r.size() - 1;
            while (x < y)
            {
                size_t const mid = (x + y) / 2;
                if (r[mid](h[i]) <= r[mid + 1](h[i]))
                    y = mid;
                else
                    x = mid + 1;
            }
            f[i] = min(f[i], r[x](h[i]) + h[i] * h[i] + w[i - 1]);
        }
    vector<linear_fn> s = cdq((a + b) / 2 + 1, b), t;
    auto it = r.begin(), jt = s.begin();
    while (it != r.end() && jt != s.end())
        if (it->m > jt->m || (it->m == jt->m && it->t < jt->t))
            add_function(t, *it++);
        else
            add_function(t, *jt++);
    while (it != r.end())
        add_function(t, *it++);
    while (jt != s.end())
        add_function(t, *jt++);
    return t;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    cin >> n;
    for (size_t i = 0; i < n; ++i)
        cin >> h[i];
    for (size_t i = 0; i < n; ++i)
        cin >> w[i];
    for (size_t i = 1; i < n; ++i)
        w[i] += w[i - 1];
    for (size_t i = 1; i < n; ++i)
        f[i] = (h[i] - h[0]) * (h[i] - h[0]) + w[i - 1] - w[0];
    cdq(1, n - 1);
    cout << f[n - 1] << '\n';
}

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