#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 1e6 + 6;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;
struct line
{
ll t,a,b;
ld x;
};
bool operator < (line t1, line t2)
{
if(t1.t || t2.t) return t1.x < t2.x;
else return t1.a > t2.a;
}
struct lc
{
set<line> s;
line prev(line a)
{
if(s.lower_bound(a) == s.begin()) return {-1,0,0,0};
else return *(--s.lower_bound(a));
}
line next(line a)
{
if(s.upper_bound(a) == s.end()) return {-1,0,0,0};
else return *(s.upper_bound(a));
}
void calx(line a)
{
line pa = prev(a);
if(pa.t == -1) return;
s.erase(a);
a.x = giao(pa,a);
s.insert(a);
}
ld giao(line a, line b)
{
return (ld)(a.b - b.b) / (b.a - a.a);
}
ll bad(line a)
{
line pa = prev(a);
line na = next(a);
if(pa.t == -1 || na.t == -1) return 0;
return (giao(pa,a) >= giao(pa,na));
}
void add(ll a, ll b)
{
line it;
if(s.lower_bound({0,0,a,b}) != s.end())
{
it = *s.lower_bound({0,0,a,b});
if(it.a == a)
{
if(it.b <= b) return;
s.erase(it);
}
}
it = {0,0,a,b};
s.insert(it);
if(bad(it)) s.erase(it);
else
{
while(true)
{
line pre = prev(it);
if(pre.t == -1) break;
if(bad(pre)) s.erase(pre);
else break;
}
while(true)
{
line nex = next(it);
if(nex.t == -1) break;
if(bad(nex)) s.erase(nex);
else break;
}
calx(it);
if(next(it).t != -1) calx(next(it));
}
}
ll get(ll x)
{
line ans = *(--s.upper_bound({1,x,0,0}));
return ans.a * x + ans.b;
}
};
lc f;
ll h[N],w[N],d[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >>n;
ll i,j;
for(i = 1;i <= n;i++)
{
cin >> h[i];
}
ll sum = 0;
for(i = 1;i <= n;i++)
{
cin >> w[i];
sum += w[i];
}
d[1] = -w[1];
for(i = 2;i <= n;i++)
{
f.add(-2 * h[i - 1], d[i - 1] + h[i - 1] * h[i - 1]);
d[i] = f.get(h[i]) - w[i] + h[i] * h[i];
}
cout << sum + d[n];
}
Compilation message (stderr)
building.cpp: In member function 'void lc::add(long long int, long long int)':
building.cpp:57:33: warning: narrowing conversion of 'b' from 'long long int' to 'long double' [-Wnarrowing]
57 | if(s.lower_bound({0,0,a,b}) != s.end())
| ^
building.cpp:59:40: warning: narrowing conversion of 'b' from 'long long int' to 'long double' [-Wnarrowing]
59 | it = *s.lower_bound({0,0,a,b});
| ^
building.cpp:66:21: warning: narrowing conversion of 'b' from 'long long int' to 'long double' [-Wnarrowing]
66 | it = {0,0,a,b};
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |