제출 #1184421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184421		belgianbot	Building Bridges (CEOI17_building)	C++20	0 / 100	51 ms	4164 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;
queue<pair<double,int>> change;
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 forward(int i, set<pair<double,int>>::iterator it) {

    do {
        double inter = intersection(i, it->se);
        auto it2 = convex.upper_bound({inter, -1});
        if (it2->se == it->se) {
            if (h[it->se] < h[i]) {
                change.push({inter,it->se});
                change.push({it2->fi,i});
            }
            else change.push({inter, i});
        }
        else break;
    } while (++it != convex.end());
}
void backward(int i, set<pair<double,int>>::iterator it) {

    while (it-- != convex.begin()) {
        double inter = intersection(i, it->se);
        auto it2 = convex.upper_bound({inter, -1});
        if (it2->se == it->se) {
            if (h[it->se] < h[i]) {
                change.push({inter,it->se});
                change.push({it2->fi,i});
            }
            else change.push({inter, i});
        }
        else break;
    }
}
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]) {
            backward(i, it);
            forward(i, it);

            while (!change.empty()) {
                auto x = change.front(); change.pop();
                for (set<pair<double,int>>::iterator it = convex.lower_bound({x.fi, -1}); it != convex.end() && abs(it->fi- x.fi) < 0.01;) {
                    auto it2 = it; it2++;
                    convex.erase(it);
                    it = it2;
                }
                convex.insert({x.fi, x.se});
            }
        }
        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