Submission #1193999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193999		trvhung	Building Bridges (CEOI17_building)	C++20	100 / 100	38 ms	9032 KiB

building

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int N = 1e5 + 5;
const int M = 1e6;
int n, h[N], w[N];
ll p[N], dp[N];

const ll LINF = LLONG_MAX;
struct Line {
	ll a, b;
	mutable ll p;
	bool operator < (const Line &o) const {
		if (o.a == LINF && o.b == LINF) return p < o.p;
		return a < o.a;
	}
};

struct LineContainer {
	multiset<Line> myLC;
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 && a % b);
	}

	bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) {
		if (y == myLC.end()) return x -> p = LINF, false;
		if (x -> a == y -> a) x -> p = (x -> b > y -> b ? LINF : -LINF);
		else x -> p = div(y -> b - x -> b, x -> a - y -> a);
		return x -> p >= y -> p;
	}

	void add(ll a, ll b) {
		auto x = myLC.insert({a, b, 0}), y = next(x);
		while (isect(x, y)) y = myLC.erase(y);
		if ((y = x) != myLC.begin() && isect(--y, x)) isect(y, myLC.erase(x));
		while ((x = y) != myLC.begin() && (--x) -> p >= y -> p)
			isect(x, myLC.erase(y)), y = x;
	}

	ll query(ll x) {
		Line l = *myLC.lower_bound({LINF, LINF, x});
		return l.a * x + l.b;
	}
} CHT;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	for (int i = 1; i <= n; ++i)
		cin >> w[i], p[i] = p[i - 1] + w[i];

	CHT.add(2 * h[1], p[1] - 1LL * h[1] * h[1]);
	for (int i = 2; i <= n; ++i) {
		dp[i] = 1LL * h[i] * h[i] + p[i - 1] - CHT.query(h[i]);
		CHT.add(2 * h[i], p[i] - dp[i] - 1LL * h[i] * h[i]);
	}

	cout << dp[n];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

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