oj.uz

Submission #1020666

# Submission time Handle Problem Language Result Execution time Memory
1020666 2024-07-12T08:10:15 Z NValchanov Building Bridges (CEOI17_building) C++17
100 / 100
 118 ms 67192 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63032 KB Output is correct
2 Correct 28 ms 63068 KB Output is correct
3 Correct 28 ms 63068 KB Output is correct
4 Correct 27 ms 63060 KB Output is correct
5 Correct 28 ms 62904 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 66128 KB Output is correct
2 Correct 81 ms 66128 KB Output is correct
3 Correct 75 ms 66036 KB Output is correct
4 Correct 71 ms 66132 KB Output is correct
5 Correct 76 ms 66132 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63032 KB Output is correct
2 Correct 28 ms 63068 KB Output is correct
3 Correct 28 ms 63068 KB Output is correct
4 Correct 27 ms 63060 KB Output is correct
5 Correct 28 ms 62904 KB Output is correct
6 Correct 76 ms 66128 KB Output is correct
7 Correct 81 ms 66128 KB Output is correct
8 Correct 75 ms 66036 KB Output is correct
9 Correct 71 ms 66132 KB Output is correct
10 Correct 76 ms 66132 KB Output is correct
11 Correct 118 ms 67164 KB Output is correct
12 Correct 81 ms 67156 KB Output is correct
13 Correct 100 ms 67100 KB Output is correct
14 Correct 92 ms 67192 KB Output is correct
15 Correct 80 ms 66864 KB Output is correct
16 Correct 73 ms 66896 KB Output is correct
17 Correct 83 ms 67088 KB Output is correct
18 Correct 85 ms 67080 KB Output is correct