oj.uz

Submission #860168

# Submission time Handle Problem Language Result Execution time Memory
860168 2023-10-12T01:17:57 Z Nhoksocqt1 Building Bridges (CEOI17_building) C++17
100 / 100
 35 ms 7236 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

ll dp[MAXN], sumCost[MAXN];
int height[MAXN], costRemove[MAXN], nArr;

ll brute(void) {
    for (int i = 2; i <= nArr; ++i)
        dp[i] = 1e18;

    for (int i = 1; i < nArr; ++i) {
        for (int j = i + 1; j <= nArr; ++j) {
            dp[j] = min(dp[j], dp[i] + 1LL * height[i] * height[i] + 1LL * height[j] * height[j] - 2LL * height[i] * height[j] + sumCost[j - 1] - sumCost[i]);
        }
    }

    return dp[nArr];
}

const int MINCOORD = 0;
const int MAXCOORD = 1e6;

struct Line {
    ll a, b;

    Line(ll _a = 0, ll _b = 1e18) : a(_a), b(_b) {};

    inline ll get(ll x) const {
        return a * x + b;
    }

};

struct Lichao {
    struct Node {
        Line line;
        int L, R;
    };

    vector<Node> tree;

    void init(void) {
        tree.clear();
        tree.push_back({Line(), -1, -1});
    }

    void update(int id, int l, int r, Line lines) {
        while(1) {
            Line low(lines), high(tree[id].line);
            if(low.get(l) > high.get(l))
                swap(low, high);

            tree[id].line = low;
            if(low.get(r) <= high.get(r))
                return;

            int mid = (l + r) >> 1;
            //cout << l << ' ' << r << ' ' << low.get(mid) << ' ' << high.get(mid) << ' ' << low.a << ' ' << low.b << ' ' << high.a << ' ' << high.b << '\n';
            if(low.get(mid) <= high.get(mid)) {
                if(tree[id].R == -1)
                    tree[id].R = sz(tree), tree.push_back({Line(), -1, -1});

                id = tree[id].R;
                lines = high, l = mid + 1;
            } else {
                if(tree[id].L == -1)
                    tree[id].L = sz(tree), tree.push_back({Line(), -1, -1});

                tree[id].line = high;
                id = tree[id].L;
                lines = low, r = mid;
            }
        }
    }

    ll query(int id, int l, int r, int x) {
        ll res(tree[id].line.get(x));
        while(l < r) {
            int mid = (l + r) >> 1;
            if(x <= mid) {
                id = tree[id].L;
                r = mid;
            } else {
                id = tree[id].R;
                l = mid + 1;
            }

            //cout << '.' << id << ' ' << l << ' ' << r << ' ' << x << '\n';
            if(id == -1)
                break;

            res = min(res, tree[id].line.get(x));
        }

        return res;
    }
} lichao;

ll magicFunc(void) {
    lichao.init();
    lichao.update(0, MINCOORD, MAXCOORD, Line(-2 * height[1], 1LL * height[1] * height[1] - sumCost[1]));
    for (int i = 2; i <= nArr; ++i) {
        dp[i] = lichao.query(0, MINCOORD, MAXCOORD, height[i]) + 1LL * height[i] * height[i] + sumCost[i - 1];
        lichao.update(0, MINCOORD, MAXCOORD, Line(-2 * height[i], dp[i] + 1LL * height[i] * height[i] - sumCost[i]));
        //cout << dp[i] << " \n"[i == nArr];
    }

    return dp[nArr];
}

void process(void) {
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i) {
        cin >> height[i];
        //height[i] = Random(0, 1e6); cout << height[i] << " \n"[i == nArr];
    }

    for (int i = 1; i <= nArr; ++i) {
        cin >> costRemove[i];
        //costRemove[i] = Random(-1e6, 1e6); cout << costRemove[i] << " \n"[i == nArr];
        sumCost[i] = sumCost[i - 1] + costRemove[i];
    }

    //cout << brute() << '\n';
    cout << magicFunc() << '\n';
}

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

    process();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3712 KB Output is correct
2 Correct 34 ms 3664 KB Output is correct
3 Correct 31 ms 3668 KB Output is correct
4 Correct 30 ms 3552 KB Output is correct
5 Correct 23 ms 5064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 35 ms 3712 KB Output is correct
7 Correct 34 ms 3664 KB Output is correct
8 Correct 31 ms 3668 KB Output is correct
9 Correct 30 ms 3552 KB Output is correct
10 Correct 23 ms 5064 KB Output is correct
11 Correct 28 ms 3516 KB Output is correct
12 Correct 29 ms 3756 KB Output is correct
13 Correct 26 ms 3464 KB Output is correct
14 Correct 29 ms 3676 KB Output is correct
15 Correct 26 ms 7236 KB Output is correct
16 Correct 23 ms 5076 KB Output is correct
17 Correct 17 ms 3420 KB Output is correct
18 Correct 12 ms 3416 KB Output is correct