제출 #1184691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184691		belgianbot	Building Bridges (CEOI17_building)	C++20	0 / 100	17 ms	3652 KiB

building

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

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) {
    if (h[a] == h[b]) return 0.0;
    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;
    while (it2 != convex.end()) {
        double inter = intersection(i, it2->se);
        if (h[i] == h[it->se]) {
            if (memo[it->se] - prefix(it->se, N-1) > memo[i] - prefix(i, N-1)) inter = it->fi;
            else {
                right = LLONG_MIN;
                break;
            }
            it2++;
            continue;
        }
        auto best = convex.lower_bound({inter, -1});
        right = inter;
        if (best->se == it2->se) break;
        if (h[best->se] <= h[i]) {
            right = LLONG_MIN;
            break;
        }
        it2++; 
    }
    while (it-- != convex.begin()) {
        double inter = intersection(i, it->se);
        if (h[i] == h[it->se]) {
            if (memo[it->se] - prefix(it->se, N-1) > memo[i] - prefix(i, N-1)) inter = it->fi;
            else {
                right = LLONG_MIN;
                break;
            }
            continue;
        }
        auto best = convex.lower_bound({inter,-1});
        left = inter;
        if (best->se == it->se)break;
        if (h[best->se] >= h[i]) {
            left = LLONG_MAX;
            break;
        }
    }
    if (right <= left) return;
    left = max(left, double(0.0)); right = min(right, double(1000000.0));
    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+1;
    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];
        if (!i || i == N-1) cost[i] = 0;
        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]) + prefix(i+1, it->se-1);
        
        /*if (h[i] != h[it->se])*/ convexHull(i);
        /*else if (memo[i] - prefix(i, N) < memo[it->se] - prefix(it->se, N)) {
            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