Submission #66511

#	Time	Username	Problem	Language	Result	Execution time	Memory
66511		polyfish	Building Bridges (CEOI17_building)	C++14	100 / 100	150 ms	41660 KiB

building

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int64_t MAX_N = 100002;
const int64_t INF = 1e18;

struct line {
    int64_t a, b;

    line() {}
    line(int64_t a, int64_t b):
        a(a), b(b) {}

    int64_t get(int64_t x) {
        return a * x + b;
    }
};

class IT {
public:
    struct node {
        line d;
        node *left_child, *right_child;

        node() {
            d = line(0, INF);
            left_child = NULL;
            right_child = NULL;
        }

        void make_children() {
            if (left_child==NULL) {
                left_child = new node();
                right_child = new node();
            }
        }
    };

    int64_t st, fn;
    node *root;

    IT(int64_t _n) {
        st = -2*_n;
        fn = 2*_n;
        root = new node();
    }

    void upd(line val, int64_t l, int64_t r, node *cur) {
        if (l>r)
            return;
        int64_t mid = (l + r) / 2;
        if (l==-1 && r==0)
            --mid;
        cur->make_children();
        if (val.get(l)<=cur->d.get(l) && val.get(r)<=cur->d.get(r))
            cur->d = val;
        else if (val.get(l)>=cur->d.get(l) && val.get(r)>=cur->d.get(r))
            return;
        else if (val.get(l)>=cur->d.get(l) && val.get(mid)>=cur->d.get(mid) && l!=r)
            upd(val, mid+1, r, cur->right_child);
        else if (val.get(l)<=cur->d.get(l) && val.get(mid)<=cur->d.get(mid)) {
        	if (l!=r)
            	upd(cur->d, mid+1, r, cur->right_child);
            cur->d = val;
        }
        else if (val.get(r)>=cur->d.get(r) && val.get(mid)>=cur->d.get(mid) && l!=r)
            upd(val, l, mid, cur->left_child);
        else if (val.get(r)<=cur->d.get(r) && val.get(mid)<=cur->d.get(mid)) {
            if (l!=r)
            	upd(cur->d, l, mid, cur->left_child);
            cur->d = val;
        }
    }

    int64_t get(int64_t pos, int64_t l, int64_t r, node *cur) {
        if (pos<l || pos>r)
            return INF;
        cur->make_children();
        int64_t res = cur->d.get(pos);
        if (l==r)
            return res;
        int64_t mid = (l + r) / 2;
        if (l==-1 && r==0)
            --mid;
        return min(res, min(get(pos, l, mid, cur->left_child),
                            get(pos, mid+1, r, cur->right_child)));
    }

    void upd(line val) {
        upd(val, st, fn, root);
    }

    int64_t get(int64_t pos) {
        return get(pos, st, fn, root);
    }
};

int64_t n;
int64_t h[MAX_N], w[MAX_N], f[MAX_N];

int64_t sqr(int64_t x) {
    return x * x;
}

void enter() {
    cin >> n;
    for (int64_t i=1; i<=n; ++i) {
        cin >> h[i];
    }
    for (int64_t i=1; i<=n; ++i) {
        cin >> w[i];
        w[i] += w[i-1];
    }
}

void solve() {
    IT tr(2*(*max_element(h+1, h+n+1)));
    tr.upd(line(-2*h[1], f[1] - w[1] + sqr(h[1])));
    for (int64_t i=2; i<=n; ++i) {
        f[i] = tr.get(h[i]) + w[i-1] + sqr(h[i]);
        tr.upd(line(-2*h[i], f[i] - w[i] + sqr(h[i])));
    }
    cout << f[n];
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
    solve();
}

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