제출 #1332939

#제출 시각아이디문제언어결과실행 시간메모리
1332939blackscreen1Building Bridges (CEOI17_building)C++20
0 / 100
31 ms3140 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
struct line {
	ll m, c;
	line () {m = c = 1e9;}
	line (ll M, ll C) {m = M, c = C;}
	ll operator() (ll x) {return m*x + c;}
};
struct node {
	ll s, e, m;
	line v;
	node *l, *r;
	node (ll S, ll E) {
		s = S, e = E, m = (S+E)>>1;
		v = line();
		l = nullptr;
	}
	void create() {
		if (s != e) l = new node(s, m), r = new node(m+1, e);
	}
	void upd(line V) {
		if (v(s) >= V(s)) swap(v, V);
		if (v(e) <= V(e)) return;
		if (l == nullptr) create();
		if (v(m) <= V(m)) r->upd(V);
		else l->upd(V);
	}
	ll qu(ll X) {
		if (l == nullptr) return v(X);
		if (X <= m) return min(v(X), l->qu(X));
		return min(v(X), r->qu(X));
	}
} *root = new node(0, 1000005);
ll n, a[100005], b[100005], pf[100005];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	iloop(0, n) cin >> a[i];
	iloop(0, n) {
		cin >> b[i];
		pf[i] = (i ? pf[i-1] : 0) + b[i];
	}
	b[0] = 0;
	iloop(1, n) {
		root->upd(line(-2*a[i-1], a[i-1]*a[i-1] - pf[i-1] + b[i-1]));
		b[i] = pf[i-1] + a[i]*a[i] + root->qu(a[i]);
		//cout << b[i] << " ";
	}
	cout << b[n-1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...