Submission #1184524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184524		belgianbot	Building Bridges (CEOI17_building)	C++20	0 / 100	106 ms	3596 KiB

building

#include <bits/stdc++.h>
#define fi first 
#define se second
#define int long long
#define double long double

using namespace std;

vector<int> memo, cost, h, pref;
set<pair<double,int>> convex;
int N;

int prefix(int l, int r) {
    if (l > r) return 0;
    l--;
    if (l <= 0) return pref[r];
    else return pref[r] - pref[l];
}
double intersection(int a, int b) {
    return (h[b] * h[b] + memo[b] - prefix(b, N-1) + prefix(a, N-1) - memo[a] - h[a] * h[a]) / ((double)(2*(h[b] - h[a])));
}
void propagate(int i, set<pair<double,int>>::iterator it) {
    double left = 0, right = 1000000;
    auto it2 = it;
    bool tried = false;
    while (it2 != convex.end()) {
        tried = true;
        double inter = intersection(i, it2->se);
        auto best = convex.lower_bound({inter, -1});
        right = inter;
        if (best->se == it2->se) break;
        it2++; 
    }
    while (it-- != convex.begin()) {
        tried == true;
        double inter = intersection(i, it->se);
        auto best = convex.lower_bound({inter,-1});
        left = inter;
        if (best->se == it->se)break;
    }
    //if ((!left && right == 1000000 && tried) || right < 0 || left > 1e6) return;
    auto it3 = convex.lower_bound({left, -1});
    int index = -1;
    if (it3->fi <= right) index = it3->se;
    for (; it3 != convex.end() && it3->fi <= right;) {
        auto it4 = it3; it4++;
        convex.erase(it3);
        it3 = it4;
    }
    if (index != -1 && left)convex.insert({left, index});
    convex.insert({right, i});
}
void convexHull(int i) {
    double l = 0.0, r = 1e6;
    while (r - l > 0.0001) {
        double mid = (l + r) / 2.0;
        auto it = convex.lower_bound({mid,-1});
        if (h[it->se] > h[i]) {
            auto it2 = it; it2--;
            if (it == convex.begin() || h[it2->se] <= h[i]) {
                propagate(i, it);
                break;
            }
            r = mid;
        }
        else {
            auto it2 = it; it2++;
            if (it2 == convex.end() || h[it2->se] > h[i]) {
                propagate(i, it2);
                break;
            }
            l = mid;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    memo.resize(N, -1); cost.resize(N); h.resize(N); pref.resize(N, 0);
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N; i++) {
        if (i) pref[i] = pref[i-1];
        cin >> cost[i];
        pref[i] += cost[i];
    }

    memo[N-1] = 0;

    convex.insert({1e6, N-1});
    for (int i = N - 2; i >= 0; i--) {
        auto it = convex.lower_bound({h[i], -1});
        memo[i] = memo[it->se] + (h[i] - h[it->se]) * (h[i] - h[it->se]) + pref[it->se-1] - pref[i];
        
        if (h[i] != h[it->se]) {
            convexHull(i);
        }
        else if (memo[i] - prefix(i, N-1) < memo[it->se] - prefix(it->se, N-1)) {
            convex.insert({it->fi, i});
            convex.erase(it);
        }
        
    }
    cout << memo[0] << '\n';
    return 0;
}

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