Submission #1146161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146161		wikidere	Building Bridges (CEOI17_building)	C++17	100 / 100	30 ms	12616 KiB

building

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
 
typedef long long ll;
 
// Structure representing a line of the form f(x)= m*x + b.
struct Line {
    ll m, b;
    Line(ll _m = 0, ll _b = LLONG_MAX) : m(_m), b(_b) {}
    ll eval(ll x) const {
        return m * x + b;
    }
};
 
// LiChao tree implementation to maintain a set of lines and answer minimum queries.
struct LiChao {
    struct Node {
        Line line;
        Node *l, *r;
        Node(Line line): line(line), l(nullptr), r(nullptr) {}
    };
    
    Node* root;
    ll L, R;
    
    // The tree covers x in [L, R)
    LiChao(ll l, ll r) : L(l), R(r) {
        root = new Node(Line(0, LLONG_MAX)); // initial dummy line with "infinite" cost.
    }
    
    // Add a new line to the structure.
    void addLine(Line newline) {
        addLine(root, L, R, newline);
    }
    
    void addLine(Node* node, ll l, ll r, Line newline) {
        ll mid = (l + r) >> 1;
        bool left = newline.eval(l) < node->line.eval(l);
        bool mVal = newline.eval(mid) < node->line.eval(mid);
        if(mVal) {
            // Swap the lines.
            Line temp = node->line;
            node->line = newline;
            newline = temp;
        }
        if(r - l == 1) return; // reached a leaf interval.
        if(left != mVal) {
            if(!node->l) node->l = new Node(Line(0, LLONG_MAX));
            addLine(node->l, l, mid, newline);
        } else {
            if(!node->r) node->r = new Node(Line(0, LLONG_MAX));
            addLine(node->r, mid, r, newline);
        }
    }
    
    // Query the minimum value at point x.
    ll query(ll x) {
        return query(root, L, R, x);
    }
    
    ll query(Node* node, ll l, ll r, ll x) {
        if(!node) return LLONG_MAX;
        ll mid = (l + r) >> 1;
        ll cur = node->line.eval(x);
        if(r - l == 1) return cur;
        if(x < mid)
            return min(cur, query(node->l, l, mid, x));
        else
            return min(cur, query(node->r, mid, r, x));
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; 
    cin >> n;
    vector<ll> h(n+1), w(n+1);
    for (int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> w[i];
    }
    
    // Precompute prefix sums of removal costs.
    vector<ll> pref(n+1, 0);
    for (int i = 1; i <= n; i++){
        pref[i] = pref[i-1] + w[i];
    }
    
    // dp[i]: minimum cost to build a valid bridge ending at pillar i.
    vector<ll> dp(n+1, 0);
    dp[1] = 0; // starting at the first pillar.
    
    // LiChao tree for x in [0, 1e6+1). Since 0 <= h[i] <= 1e6.
    ll Xlow = 0, Xhigh = 1000001;
    LiChao tree(Xlow, Xhigh);
    
    // For the first pillar, add the corresponding line:
    // slope = -2*h[1], intercept = dp[1] - pref[1] + h[1]^2.
    tree.addLine(Line(-2LL * h[1], dp[1] - pref[1] + h[1]*h[1]));
    
    for (int i = 2; i <= n; i++){
        // Query the minimum value at x = h[i].
        ll best = tree.query(h[i]);
        // Compute dp[i] using the recurrence.
        dp[i] = pref[i-1] + h[i]*h[i] + best;
        // Add the line corresponding to pillar i.
        tree.addLine(Line(-2LL * h[i], dp[i] - pref[i] + h[i]*h[i]));
    }
    
    cout << dp[n] << "\n";
    return 0;
}

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