oj.uz

Submission #66189

# Submission time Handle Problem Language Result Execution time Memory
66189 2018-08-10T03:08:51 Z polyfish Building Bridges (CEOI17_building) C++14
30 / 100
 620 ms 132096 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 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;
        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, 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 3 ms 376 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5328 KB Output is correct
2 Correct 66 ms 5328 KB Output is correct
3 Correct 71 ms 5328 KB Output is correct
4 Correct 57 ms 5328 KB Output is correct
5 Runtime error 620 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 79 ms 5328 KB Output is correct
7 Correct 66 ms 5328 KB Output is correct
8 Correct 71 ms 5328 KB Output is correct
9 Correct 57 ms 5328 KB Output is correct
10 Runtime error 620 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)