Submission #972130

#	Time	Username	Problem	Language	Result	Execution time	Memory
972130		efedmrlr	Building Bridges (CEOI17_building)	C++17	100 / 100	64 ms	22472 KiB

building

#include <bits/stdc++.h>

#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const lli INF = 1e17;

struct Line {
    lli a, b;
    Line() {}
    Line(lli aa, lli bb) : a(aa), b(bb) {}
    ld intersect(Line &oth) {
        return (ld)(oth.b - b) / (a - oth.a);
    }
    lli eval(int x) {
        return a * x + b;
    }
    bool operator<(Line &oth) {
        return a < oth.a;
    }
    
    void print() {
        cout << a << " x + " << b << "\n";
    }
};

struct Node {
    Line x;
    int lc, rc;
    Node() : x(Line(0, INF)), lc(-1), rc(-1) {}
};

struct LiChao {
    const int MX = 1e6 + 5;
    vector<Node> st;
    int pt;
    int create_node() {
        st.pb(Node()); 
        return pt++;
    }
    void reset() {
        pt = 0;
        st.clear();
        create_node();
    }
    void extend(int v) {
        if(st[v].lc == -1) st[v].lc = create_node();
        if(st[v].rc == -1) st[v].rc = create_node();
    } 
    void update(int tl, int tr, int v, Line nw) {
        if(nw.a == st[v].x.a) {
            if(nw.b < st[v].x.b) {
                swap(nw, st[v].x);
            }
            return;
        }
        if(tl == tr) {
            if(nw.eval(tl) < st[v].x.eval(tl)) {
                st[v].x = nw;
            }
            return;
        } 
        extend(v);
        int tm = (tl + tr) >> 1;
        if(nw.a > st[v].x.a) {
            swap(nw, st[v].x);
        } 
        ld inter = nw.intersect(st[v].x);
        if(inter < (ld)tm) {
            swap(st[v].x, nw);
            update(tl, tm, st[v].lc, nw);
        }
        else {
            update(tm + 1, tr, st[v].rc, nw);
        }
    }
    void update(Line nw) {
        // nw.print();
        update(0, MX, 0, nw);
    }
    lli query(int tl, int tr, int v, int ind) {
        if(tl == tr) {
            return st[v].x.eval(ind);
        }
        int tm = (tl + tr) >> 1;
        extend(v);
        if(ind <= tm) {
            return min(query(tl, tm, st[v].lc, ind), st[v].x.eval(ind));
        } 
        else {
            return min(query(tm + 1, tr, st[v].rc, ind), st[v].x.eval(ind));
        }
    }
    lli query(int ind) {
        return query(0, MX, 0, ind);
    }

};
LiChao st;
vector<int> h(N), w(N);
vector<lli> dp(N, INF), pr(N, 0);
void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for(int i = 1; i <= n; i++) {
        pr[i] = pr[i - 1] + w[i];
    }
    dp[1] = 0;
    st.reset();
    st.update(Line(-2 * h[1], h[1] * h[1] - pr[1] + dp[1]));
    for(int i = 2; i <= n; i++) {
        dp[i] = st.query(h[i]) + pr[i - 1] + h[i] * h[i];
        st.update(Line(-2 * h[i], h[i] * h[i] - pr[i] + dp[i]));
    }
    cout << dp[n];
}

signed main() {
    fastio();
    solve();
}

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