제출 #94608

#제출 시각아이디문제언어결과실행 시간메모리
94608jasony123123Building Bridges (CEOI17_building)C++11
100 / 100
77 ms17272 KiB
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/********************CEOI 2017 Day 2 Problem 1******************************/

struct Line {
	ll m, b;
	Line() {} 
	Line(ll _m, ll _b) : m(_m), b(_b) {}
	inline ll eval(int x) { return m*x + b; }
};

struct TNode {
	const static int SZ = 1000000;
	Line data;
	TNode* C[2];

	TNode() {
		C[0] = C[1] = NULL;
		data = Line(0, LLONG_MAX); // change for min/max
	}

	inline TNode* get(int c) {
		if (!C[c]) C[c] = new TNode();
		return C[c];
	}

	void upd(Line nLine, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		if (nLine.eval(mid) < data.eval(mid)) swap(nLine, data);
		if (L == R) return;
		if (nLine.eval(L) < data.eval(L)) get(0)->upd(nLine, L, mid);
		else get(1)->upd(nLine, mid + 1, R);
	}

	ll query(int x, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		ll s = data.eval(x);
		if (L < R) {
			if (x <= mid) minn(s, get(0)->query(x, L, mid));
			else minn(s, get(1)->query(x, mid + 1, R));
		}
		return s;
	}
};

const int MAXN = 100000;
int N;
ll H[MAXN], W[MAXN];
TNode tree;

int main() {
	io();
	cin >> N;
	FOR(i, 0, N) cin >> H[i];
	FOR(i, 0, N) cin >> W[i];
	FOR(i, 1, N) W[i] += W[i - 1];
	tree.upd(Line(-2 * H[0], H[0] * H[0] + 0 - W[0]));
	FOR(i, 1, N) {
		ll dp = tree.query(H[i]) + W[i - 1] + H[i] * H[i];
		if (i == N - 1) {
			cout << dp << "\n";
		}
		tree.upd(Line(-2 * H[i], H[i] * H[i] + dp - W[i]));
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...