Submission #97948

#	Time	Username	Problem	Language	Result	Execution time	Memory
97948		popovicirobert	Building Bridges (CEOI17_building)	C++14	100 / 100	137 ms	31224 KiB

building

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

int h[MAXN + 1], w[MAXN + 1];
ll dp[MAXN + 1];

class Batch { // min

private:

    static const ll INF = 1e18;

    struct Line {
        ll a, b;
        inline ll get(ll x) {
            return 1LL * a * x + b;
        }
    };

    struct LiChao {
        LiChao *st, *dr;
        Line l;
        LiChao() {
            st = dr = NULL;
            l = {0, INF};
        }
    }*root;


public:

    Batch() {
        root = new LiChao;
    }

    inline void fix(LiChao *nod) {
        if(nod -> st == NULL) nod -> st = new LiChao;
        if(nod -> dr == NULL) nod -> dr = new LiChao;
    }

    void add(LiChao *nod, ll left, ll right, Line l) {
        fix(nod);
        Line &cur = nod -> l;
        if(l.get(left) <= cur.get(left) && l.get(right) <= cur.get(right)) {
            cur = l;
            return ;
        }
        if(l.get(left) >= cur.get(left) && l.get(right) >= cur.get(right)) {
            return ;
        }
        ll mid = (left + right) / 2;
        if(cur.get(left) > l.get(left)) {
            swap(l, cur);
        }
        if(cur.get(mid) > l.get(mid)) {
            swap(l, cur);
            add(nod -> st, left, mid, l);
        }
        else add(nod -> dr, mid + 1, right, l);
    }

    ll query(LiChao *nod, ll left, ll right, ll x) {
        fix(nod);
        ll cur = nod -> l.get(x);
        if(left == right) {
            return cur;
        }
        ll mid = (left + right) / 2;
        if(x <= mid) return min(cur, query(nod -> st, left, mid, x));
        return min(cur, query(nod -> dr, mid + 1, right, x));
    }

    void add(Line l) {
        add(root, 0, 1e9, l);
    }

    ll query(ll x) {  // x >= 0
        return query(root, 0, 1e9, x);
    }

};

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> h[i];
    }
    ll sum = 0;
    for(i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    Batch hull;
    hull.add({-2 * h[1], 1LL * h[1] * h[1] - w[1]});
    for(i = 2; i <= n; i++) {
        dp[i] = hull.query(h[i]) + 1LL * h[i] * h[i] - w[i];
        hull.add({-2 * h[i], 1LL * h[i] * h[i] + dp[i]});
    }
    cout << dp[n] + sum;
    //cin.close();
    //cout.close();
    return 0;
}

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