제출 #713467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713467		Astrayt	Building Bridges (CEOI17_building)	C++17	100 / 100	78 ms	67252 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair

struct Line{
	int m, k;
	int val(int x){
		return m * x + k;
	}
};

Line node[4000050];

void modify(int i, int l, int r, Line L){
	int mid = (l + r) / 2;
	if(node[i].val(mid) > L.val(mid)) swap(L, node[i]);
	if(l == r) return;
	if(L.m == node[i].m) L = node[i];
	if(L.m > node[i].m) modify(2 * i, l, mid, L);
	else modify(2 * i + 1, mid + 1, r, L);
}

int query(int i, int l, int r, int pos){
	int ret = node[i].val(pos);
	if(l == r) return ret;
	int mid = (l + r) / 2;
	if(pos <= mid) return min(ret, query(2 * i, l, mid, pos));
	else return min(ret, query(2 * i + 1, mid + 1, r, pos));
}

void solve(){
	int n; cin >> n;
	vector<int> h(n + 1), w(n + 1), dp(n + 1), S(n + 1);
	for(int i = 1; i <= n; ++i) cin >> h[i];
	for(int i = 1; i <= n; ++i) cin >> w[i], S[i] = S[i - 1] + w[i];
	for(auto &L:node){
		L.m = -2 * h[1];
		L.k = h[1] * h[1] - S[1];
	}
	for(int i = 2; i <= n; ++i){
		dp[i] = query(1, 0, 1000000, h[i]) + h[i] * h[i] + S[i] - w[i];
		Line L;
		L.m = -2 * h[i], L.k = h[i] * h[i] + dp[i] - S[i];
		modify(1, 0, 1000000, L); 
	}
	cout << dp[n] << '\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1; //cin >> t;
	while(t--) solve();
}

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