Submission #1232626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232626		sg93	Building Bridges (CEOI17_building)	C++17	0 / 100	36 ms	3396 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define int long long

struct line{
	ll a, b;
	line(){a = 0; b = 0;}
	line(ll a, ll b){
		this->a = a;
		this->b = b;
	}
	ll operator()(int x){
		return a * x + b;
	}
};

const int M = 1e9;

struct node {
    line tr;
    node *lpt, *rpt;

    node() : tr(0, LLONG_MAX), lpt(nullptr), rpt(nullptr) {}

    int divi (int a, int b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    void update (line f, int l = 0, int r = M) {
        if (l == r) {
            tr = (f(l) < tr(l) ? f : tr);
            return;
        }
        int mid = divi(l + r, 2);
        if (f(mid) < tr(mid)) swap(tr, f);
        if (f.a > tr.a) {
            if (lpt == nullptr) lpt = new node(); // khởi tạo bộ nhớ cho cây con trái
            lpt->update(f, l, mid); // trường hợp 1.1
        }
        if (f.a < tr.a) {
            if (rpt == nullptr) rpt = new node(); // khởi tạo bộ nhớ cho cây con phải
            rpt->update(f, mid + 1, r); // trường hợp 1.2
        }
    }

    ll query (int pos, int l = 0, int r = M) {
        ll cur = tr(pos);
        int mid = divi(l + r, 2);
        if (l == r) return cur;
        if (pos <= mid)
            return min(cur, lpt == nullptr ? LLONG_MAX : lpt->query(pos, l, mid));
        else
            return min(cur, rpt == nullptr ? LLONG_MAX : rpt->query(pos, mid + 1, r));
    }
};

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n; cin >> n;
	int h[n + 1], w[n + 1], s[n + 1];
	s[0] = 0;
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		s[i] = s[i - 1] + w[i];
	}
	ll dp;
	node lich;
	lich.update(line(-2 * h[1], h[1] * h[1]));
	ll mn = LLONG_MAX;
	for(int i = 2; i <= n; i++){
		dp = h[i] * h[i] + lich.query(h[i]) + s[i - 1];
		lich.update(line(-2 * h[i], h[i] * h[i] - s[i] + dp));
	}
	cout << dp << " ";

}

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