Submission #860168

#	Time	Username	Problem	Language	Result	Execution time	Memory
860168		Nhoksocqt1	Building Bridges (CEOI17_building)	C++17	100 / 100	35 ms	7236 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40