Submission #94603

#	Time	Username	Problem	Language	Result	Execution time	Memory
94603		jasony123123	Building Bridges (CEOI17_building)	C++11	100 / 100	107 ms	64604 KiB

building

#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; }
};

template <int SZ> struct LiChao {
	int n;
	Line st[SZ * 4];

	LiChao() {}

	void init(Line def, int N = SZ) {
		fill(st, st + N*4, def);
	}

	void upd(Line nLine, int ind = 1, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		if (nLine.eval(mid) < st[ind].eval(mid)) swap(nLine, st[ind]);
		if (L == R) return;
		if (nLine.eval(L) < st[ind].eval(L)) upd(nLine, 2 * ind, L, mid);
		else upd(nLine, 2 * ind + 1, mid + 1, R);
	}

	ll query(int x, int ind = 1, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		ll s = st[ind].eval(x);
		if (L < R) {
			if (x <= mid) s = min(query(x, 2 * ind, L, mid), s);
			else s = min(query(x, 2 * ind + 1, mid + 1, R), s);
		}
		return s;
	}
};

const int MAXN = 100000;
int N;
ll H[MAXN], W[MAXN];
LiChao<1000001> 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];
//	darr(W, N);
//	darr(H, N);
	tree.init(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]));
	}
}

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