oj.uz

Submission #66511

# Submission time Handle Problem Language Result Execution time Memory
66511 2018-08-11T09:02:22 Z polyfish Building Bridges (CEOI17_building) C++14
100 / 100
 150 ms 41660 KB 
//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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 3 ms 584 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 5396 KB Output is correct
2 Correct 107 ms 6400 KB Output is correct
3 Correct 90 ms 7448 KB Output is correct
4 Correct 68 ms 7448 KB Output is correct
5 Correct 106 ms 29228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 3 ms 584 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 109 ms 5396 KB Output is correct
7 Correct 107 ms 6400 KB Output is correct
8 Correct 90 ms 7448 KB Output is correct
9 Correct 68 ms 7448 KB Output is correct
10 Correct 106 ms 29228 KB Output is correct
11 Correct 150 ms 29228 KB Output is correct
12 Correct 133 ms 29228 KB Output is correct
13 Correct 58 ms 29228 KB Output is correct
14 Correct 144 ms 29228 KB Output is correct
15 Correct 121 ms 41660 KB Output is correct
16 Correct 87 ms 41660 KB Output is correct
17 Correct 51 ms 41660 KB Output is correct
18 Correct 36 ms 41660 KB Output is correct