#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e6+5;
pair <int,int> t[N*4];
void build(int v,int tl,int tr){
t[v]={1e9,1e18};
if(tl!=tr){
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
}
}
int f(int m,int x,int c){
return m*x+c;
}
void insert(int v,int tl,int tr,int m,int c){
if(tl==tr){
if(f(t[v].ff,tl,t[v].ss)>=f(m,tl,c))t[v]={m,c};
}
else{
int tm=(tl+tr)/2;
if(t[v].ff>m){
swap(m,t[v].ff);
swap(c,t[v].ss);
}
if(f(t[v].ff,tm,t[v].ss)<=f(m,tm,c)){
insert(v*2,tl,tm,m,c);
}
else{
insert(v*2,tm+1,tr,t[v].ff,t[v].ss);
t[v]={m,c};
}
}
}
int get(int v,int tl,int tr,int x){
if(tl==tr)return f(t[v].ff,x,t[v].ss);
int tm=(tl+tr)/2;
if(x<=tm)return min(f(t[v].ff,x,t[v].ss),get(v*2,tl,tm,x));
else return min(f(t[v].ff,x,t[v].ss),get(v*2+1,tm+1,tr,x));
}
signed main(){
int n;
cin>>n;
vector <int> h(n+1),w(n+1),dp(n+1);
for(int i=1;i<=n;i++)cin>>h[i];
int sum=0;
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
build(1,1,1e6);
insert(1,1,1e6,-2*h[1],-w[1]+h[1]*h[1]);
for(int i=2;i<=n;i++){
dp[i]=get(1,1,1e6,h[i])+h[i]*h[i]-w[i];
insert(1,1,1e6,-2*h[i],dp[i]+h[i]*h[i]);
}
cout<<dp[n]+sum<<"\n";
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33624 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
33372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
35664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33624 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
33372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
