oj.uz

Submission #66182

# Submission time Handle Problem Language Result Execution time Memory
66182 2018-08-10T01:26:36 Z polyfish Building Bridges (CEOI17_building) C++14
0 / 100
 86 ms 23608 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 "building"

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 n;
    node *root;

    IT(int64_t _n) {
        n = _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;
        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))
            upd(val, mid+1, r, cur->right_child);
        else if (val.get(l)<=cur->d.get(l) && val.get(mid)<=cur->d.get(mid)) {
            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))
            upd(val, l, mid, cur->left_child);
        else if (val.get(r)<=cur->d.get(r) && val.get(mid)<=cur->d.get(mid)) {
            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;
        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, 1, n, root);
    }

    int64_t get(int64_t pos) {
        return get(pos, 1, n, 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(*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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4396 KB Output is correct
2 Correct 64 ms 4396 KB Output is correct
3 Correct 72 ms 4456 KB Output is correct
4 Correct 58 ms 4456 KB Output is correct
5 Incorrect 86 ms 23608 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Incorrect 2 ms 488 KB Output isn't correct
4 Halted 0 ms 0 KB -