Submission #1288628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288628		Jawad_Akbar_JJ	Building Bridges (CEOI17_building)	C++20	100 / 100	82 ms	7448 KiB

building

#include <iostream>

using namespace std;
#define int long long
const int N = (1<<20) + 1;
int dp[N], m[N], c[N], Line[N<<1], pre[N], h[N];

int getVal(int id, int x){
	if (id == 0) return 1e17;
	return m[id] * x + c[id];
}

void insert(int id, int cur = 1, int st = 1, int en = N){
	bool A = getVal(id, st) < getVal(Line[cur], st), B = getVal(id, en - 1) < getVal(Line[cur], en - 1);
	if (Line[cur] == 0 or A + B == 2){
		Line[cur] = id;
		return;
	}
	if (A + B == 0)
		return;

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(id, lc, st, mid);
	insert(id, rc, mid, en);
}

int get(int i, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return getVal(Line[cur], i);
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;

	if (i < mid)
		return min(getVal(Line[cur], i), get(i, lc, st, mid));
	return min(getVal(Line[cur], i), get(i, rc, mid, en));
}

signed main(){
	int n;
	cin>>n;

	for (int i=1;i<=n;i++)
		cin>>h[i];

	for (int j=1;j<=n;j++)
		cin>>pre[j], pre[j] += pre[j-1];

	m[1] = -2 * h[1], c[1] = h[1] * h[1] - pre[1];
	insert(1);

	for (int i=2;i<=n;i++){
		dp[i] = get(h[i]) + pre[i-1] + h[i] * h[i];

		m[i] = -2 * h[i];
		c[i] = dp[i] + h[i] * h[i] - pre[i];

		insert(i);
	}
	cout<<dp[n]<<'\n';
}

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