제출 #1272056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272056		iamhereforfun	Building Bridges (CEOI17_building)	C++20	30 / 100	51 ms	6880 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 int INF = 1e9 + 5;
const long long MOD = 3e18 + 7;
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;

struct Line
{
    int a, b;
    Line()
    {
        a = 0;
        b = INF;
    }
    Line(int x, int y)
    {
        a = x;
        b = y;
    }
    double intersect(Line &l)
    {
        return 1.0 * (b - l.b) / (a - l.a);
    }
    long long get(int x)
    {
        return a * x + b;
    }
};

struct Node
{
    Line node;
    Node *le, *ri;
    int div(int l, int r)
    {
        if (l + r > 0)
            return (l + r) / 2;
        else
            return (l + r - 1) / 2;
    }
    void update(Line cur, int l, int r)
    {
        if (l == r)
        {
            if (cur.get(l) < node.get(l))
            {
                node = cur;
            }
        }
        else
        {
            int m = div(l, r);
            if (node.get(m) > cur.get(m))
            {
                swap(node, cur);
            }
            if (cur.a > node.a)
            {
                if (le == NULL)
                    le = new Node();
                le->update(cur, l, m);
            }
            else if (cur.a < node.a)
            {
                if (ri == NULL)
                    ri = new Node();
                ri->update(cur, m + 1, r);
            }
        }
    }
    int get(int pos, int l, int r)
    {
        int val = node.get(pos);
        if (l == r)
        {
            return val;
        }
        else
        {
            int m = div(l, r);
            if (pos <= m)
            {
                if (le != NULL)
                    val = min(le->get(pos, l, m), val);
            }
            else
            {
                if (ri != NULL)
                    val = min(ri->get(pos, m + 1, r), val);
            }
            return val;
        }
    }
} *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->node = {0, INF};
    root->update({-2 * h[1], h[1] * h[1] - pref[1]}, -INF, INF);
    for (int x = 2; x <= n; x++)
    {
        long long best = root->get(h[x], -INF, INF);
        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]}, -INF, INF);
    }
    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: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40