#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
// segment add min get, returns INF if no segment added
struct Line{
ll a = 0, b = INF;
};
struct Lichao {
vector<Line> L;
vector<ll> x;
int N, m;
Lichao(vector<ll> dom){
N = 1;
x = dom;
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
N = x.size();
L.resize(N*4+1, Line());
};
bool better(Line a, Line b, ll x){
return a.a*x + a.b < b.a*x + b.b;
}
void addline(int node, int low, int high, Line e){
int mid = (low+high)/2;
bool doml = better(e, L[node], x[low]);
bool domm = better(e, L[node], x[mid]);
if(domm) swap(e, L[node]);
if(low+1 == high) return;
if(doml != domm){
addline(node*2, low, mid, e);
}else{
addline(node*2+1, mid, high, e);
}
}
void add(Line e){
addline(1, 0, N, e);
}
ll query(int node, int low, int high, int i){
ll res = L[node].a*x[i] + L[node].b;
if(low+1 == high) return res;
int mid = (low+high)/2;
if(i < mid){
return min(res, query(node*2, low, mid, i));
}else{
return min(res, query(node*2+1, mid, high, i));
}
}
ll query(ll v){
int k = lower_bound(x.begin(), x.end(), v) - x.begin();
return query(1, 0, N, k);
}
};
void solve(){
int n;
cin >> n;
vector<ll> h(n+1), w(n+1);
for(int i = 1; i <= n; i++){
cin >> h[i];
}
ll tot = 0;
for(int i = 1; i <= n; i++){
cin >> w[i];
tot += w[i];
}
vector<ll> dom;
for(int i = 1; i <= n; i++){
dom.push_back(h[i]);
}
Lichao T(dom);
vector<ll> f(n+1, 0);
f[1] = -w[1];
T.add({-h[1]*2, f[1]+h[1]*h[1]});
for(int i = 2; i <= n; i++){
f[i] = T.query(h[i]) + h[i]*h[i] - w[i];
T.add({-h[i]*2, f[i]+h[i]*h[i]});
//cout << f[i] << " ";
}
cout << f[n]+tot;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("main.inp", "r", stdin);
//freopen("main.out", "w", stdout);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |