제출 #727639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727639		NeroZein	Building Bridges (CEOI17_building)	C++17	60 / 100	3082 ms	7588 KiB

building

#include <bits/stdc++.h>
#define int long long 
using namespace std;
 
const int N = 100005;
const int M = 1000006;
 
struct Line {
	int m, b;
	Line () {}
	Line (int m_, int b_ ) : m(m_), b(b_) {}
	int val (int x) {
		return m * x + b; 
	}
};
 
int rt, idd; 
int L[N << 2], R[N << 2]; 
Line seg[N << 2];
 
inline void upd (int& nd, int l, int r, Line line) {
	if (nd == 0) {
		nd = ++idd;
		assert(nd < N * 4); 
		seg[nd] = line;
		return; 
	}
	int mid = (l + r) >> 1; 
	bool f1 = line.val(l) < seg[nd].val(l);
	bool f2 = line.val(mid) < seg[nd].val(mid); 
	if (f2) {
		swap(seg[nd], line);
	}
	if (f1 != f2) {
		return upd(L[nd], l, mid, line); 
	} else {
		return upd(R[nd], mid + 1, r, line); 
	}
}
 
inline int qry (int nd, int l, int r, int x) {
	int me = seg[nd].val(x);
	if (!nd) {
		return 1e18; 
	}
	if (l == r) {
		return me; 
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		return min(me, qry(L[nd], l, mid, x));
	} else {
		return min(me, qry(R[nd], mid + 1, r, x)); 
	}
}
 
int n;
int h[N], w[N];
int pref[N]; 
int dp[N]; 
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		pref[i] = pref[i - 1] + w[i];
	}
	upd(rt, 0, M, Line(-2 * h[1], h[1] * h[1] - pref[1]));
	for (int i = 2; i <= n; ++i) {
		dp[i] = h[i] * h[i] + pref[i - 1] + qry(rt, 0, M, h[i]);
		upd(rt, 0, M, Line(-2 * h[i], h[i] * h[i] - pref[i] + dp[i])); 
	}
	cout << dp[n] << '\n';
}

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