Submission #1236283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236283		sg93	Building Bridges (CEOI17_building)	C++17	0 / 100	16 ms	3568 KiB

building

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF_A = 1000000000; // 1e9

struct line {
    ll a, b;
    line(ll _a=0, ll _b=LLONG_MAX): a(_a), b(_b) {}
    ll operator()(int x) const {
        __int128 t = (__int128)a * x + b;
        return (ll)t;
    }
};

struct node {
    line tr;
    node *L = nullptr, *R = nullptr;

    void update(line f, int l = 0, int r = INF_A) {
        int mid = (l + r) >> 1;
        // nếu f tốt hơn tr tại mid, hoán đổi
        if (f(mid) < tr(mid)) 
            swap(f, tr);
        if (l == r) 
            return;
        // dựa vào hệ số góc của f (sau hoán đổi) để xuống trái/phải
        if (f.a < tr.a) { // f dốc nhẹ hơn → nhánh trái
            if (!L) L = new node();
            L->update(f, l, mid);
        } else if (f.a > tr.a) { // f dốc hơn → nhánh phải
            if (!R) R = new node();
            R->update(f, mid+1, r);
        }
    }

    ll query(int x, int l = 0, int r = INF_A) const {
        ll res = tr(x);
        if (l == r) return res;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            if (L) res = min(res, L->query(x, l, mid));
        } else {
            if (R) res = min(res, R->query(x, mid+1, r));
        }
        return res;
    }
};

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

    int n; 
    cin >> n;
    vector<ll> h(n+1), w(n+1), s(n+1, 0);
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }

    vector<ll> dp(n+1, 0);
    node lich;
    // khởi tạo với i = 1
    lich.update(line(-2*h[1], h[1]*h[1] - s[1] + dp[1]));
    for(int i = 2; i <= n; i++){
        dp[i] = h[i]*h[i] + s[i-1] + lich.query(h[i]);
        lich.update(line(-2*h[i], h[i]*h[i] - s[i] + dp[i]));
    }
    cout << dp[n] << "\n";
    return 0;
}

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