Submission #1259056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259056		paulcode	Building Bridges (CEOI17_building)	C++17	100 / 100	30 ms	7492 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5; // cần +5 tránh lỗi biên
const ll INF = 1e18;

ll h[N], w[N], dp[N];

struct Line {
    ll a, b; // y = a*x + b
    Line(ll _a=0, ll _b=INF): a(_a), b(_b) {}
    ll operator()(ll x) const { return a * x + b; }
};

struct LiChao {
    struct Node {
        Line ln;
        Node *l, *r;
        Node(Line _ln): ln(_ln), l(nullptr), r(nullptr) {}
    };
    Node* root;
    ll L, R;
    LiChao(ll _L, ll _R) : root(nullptr), L(_L), R(_R) {}

    void add_line(Line nw){ add_line(root, L, R, nw); }
    ll query(ll x){ return query(root, L, R, x); }

    void add_line(Node* &nd, ll l, ll r, Line nw){
        if(!nd){ nd = new Node(nw); return; }
        ll mid = (l+r)>>1;
        bool lef = nw(l) < nd->ln(l);
        bool mdd = nw(mid) < nd->ln(mid);
        if(mdd) swap(nw, nd->ln);
        if(l == r) return;
        if(lef != mdd) add_line(nd->l, l, mid, nw);
        else add_line(nd->r, mid+1, r, nw);
    }

    ll query(Node* nd, ll l, ll r, ll x){
        if(!nd) return INF;
        ll res = nd->ln(x);
        if(l == r) return res;
        ll mid = (l+r)>>1;
        if(x <= mid) return min(res, query(nd->l, l, mid, x));
        else return min(res, query(nd->r, mid+1, r, x));
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    long long W = 0;
    for(int i=1;i<=n;i++){ cin >> w[i]; W += w[i]; }

    const ll XMAX = 1'000'000; // max h_i
    LiChao lichao(0, XMAX);

    dp[1] = -w[1]; 
    lichao.add_line({-2*h[1], dp[1] + h[1]*h[1]});

    for(int i=2;i<=n;i++){
        ll best = lichao.query(h[i]);
        dp[i] = (h[i]*h[i] - w[i]) + best;
        lichao.add_line({-2*h[i], dp[i] + h[i]*h[i]});
    }

    cout << dp[n] + W << "\n";
    return 0;
}

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