제출 #1272062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272062		iamhereforfun	Building Bridges (CEOI17_building)	C++20	0 / 100	30 ms	6776 KiB

building

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 2e5 + 5;
const int Q = 3e5 + 5;
const int B = 1;
const int LG = 31;
const long long INF = 1e18 + 5;
const long long MOD = 3e18 + 7;
const int L = 0;
const int R = 1e6 + 5;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

struct Line
{
    long long a, b;
    long long cal(long long i)
    {
        return a * i + b;
    }
};

struct Node
{
    Line f;
    Node *le, *ri;
    long long div(long long l, long long r)
    {
        if (l + r > 0)
        {
            return (l + r) / 2;
        }
        else
        {
            return (l + r - 1) / 2;
        }
    }
    void update(Line c, long long l, long long r)
    {
        if (l == r)
        {
            if (c.cal(l) < f.cal(l))
            {
                f = c;
            }
        }
        else
        {
            long long m = div(l, r);
            if (c.cal(m) < f.cal(m))
            {
                swap(c, f);
            }
            if (c.a > f.a)
            {
                if (le == NULL)
                {
                    le = new Node();
                }
                le->update(c, l, m);
            }
            else if (c.a < f.a)
            {
                if (ri == NULL)
                {
                    ri = new Node();
                }
                ri->update(c, m + 1, r);
            }
        }
    }
    long long get(long long p, long long l, long long r)
    {
        if (l == r)
            return f.cal(p);
        long long m = div(l, r);
        long long ans = f.cal(p);
        if (p <= m)
        {
            if (le != NULL)
            {
                ans = min(ans, le->get(p, l, m));
            }
        }
        else
        {
            if (ri != NULL)
            {
                ans = min(ans, ri->get(p, m + 1, r));
            }
        }
        return ans;
    }
} *root;

int n;
long long dp[N], pref[N], h[N], c[N];

void solve()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> h[x];
    }
    pref[0] = 0;
    for (int x = 1; x <= n; x++)
    {
        cin >> c[x];
        pref[x] = pref[x - 1] + c[x];
    }
    dp[1] = 0;
    root = new Node();
    root->f = {0, INF};
    root->update({-2 * h[1], h[1] * h[1] - pref[1]}, L, R);
    for (int x = 2; x <= n; x++)
    {
        long long best = root->get(h[x], L, R);
        dp[x] = best + h[x] * h[x] + pref[x - 1];
        // cout << dp[x] << " " << x << "\n";
        root->update({-2 * h[x], h[x] * h[x] - pref[x] + dp[x]}, L, R);
    }
    cout << dp[n] << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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