#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
vector<pair<llo,llo>> cht;
vector<pair<llo,llo>> cur;
vector<pair<llo,llo>> cht2;
vector<pair<llo,llo>> cht3;
llo bl=350;
llo inf=1e19;
llo val(pair<llo,llo> x,llo y){
return x.a*y+x.b;
}
bool cmp(pair<llo,llo> x,pair<llo,llo> y){
if(x.a<y.a){
return 1;
}
else if(y.a<x.a){
return 0;
}
return x.b>y.b;
}
void update(){
if(cur.size()>bl){
sort(cur.begin(),cur.end());
reverse(cur.begin(),cur.end());
llo ind=0;
llo ind2=0;
while(ind<cur.size() and ind2<cht.size()){
if(cur[ind].a>cht[ind2].a){
cht2.pb(cur[ind]);
ind+=1;
}
else{
cht2.pb({cht[ind2]});
ind2+=1;
}
}
while(ind<cur.size() ){
cht2.pb(cur[ind]);
ind+=1;
}
while(ind2<cht.size() ){
cht2.pb(cht[ind2]);
ind2+=1;
}
/* for(auto j:cht2){
cout<<j.a<<","<<j.b<<endl;
}
cout<<endl;*/
cht.clear();
cur.clear();
for(auto j:cht2){
while(cht.size()>1){
/*if(cht[cht.size()-1].a-cht[cht.size()-2].a==j.a-cht[cht.size()-2].a){
if(cht[cht.size()-1].b<=cht[cht.size()-2].b){
cht.pop_back();
continue;
}
break;
}*/
if(cht[cht.size()-1].a==j.a and cht[cht.size()-1].b==j.b){
cht.pop_back();
continue;
}
if((cht[cht.size()-1].a-cht[cht.size()-2].a)*(cht[cht.size()-2].b-j.b)<=(-cht[cht.size()-2].a+j.a)*(cht[cht.size()-2].b-cht[cht.size()-1].b)){
cht.pop_back();
}
else{
break;
}
}
cht.pb(j);
// cout<<j.a<<","<<j.b<<endl;
}
cht2.clear();
cht3.clear();
cht3.pb({-inf,-inf});
for(int j=1;j<cht.size();j++){
cht3.pb({cht[j].b-cht[j-1].b,cht[j-1].a-cht[j].a});
if(cht3.back().b<0){
cht3.back().a=-cht3.back().a;
cht3.back().b=-cht3.back().b;
}
}
}
}
void insert(llo aa,llo bb){
cur.pb({aa,bb});
update();
}
llo bin(llo x){
llo low=0;
llo high=cht.size()-1;
llo ans=inf;
/*for(auto j:cht){
ans=min(ans,val(j,x));
}
return ans;*/
while(low<high-1){
int mid=(low+high)/2;
ans=min(ans,val(cht[mid],x));
if(x*cht3[mid].b>=cht3[mid].a){
low=mid;
}
else{
high=mid;
}
}
/*while(low<high-2){
llo mid=(low+high)/2;
llo xx=val(cht[mid-1],x);
llo yy=val(cht[mid],x);
llo zz=val(cht[mid+1],x);
ans=min(ans,min(xx,min(yy,zz)));
if(yy<xx and yy<zz){
break;
}
if(yy<zz){
high=mid;
}
else{
low=mid;
}
}*/
for(llo i=low;i<high+1;i++){
ans=min(ans,val(cht[i],x));
}
return ans;
}
llo query(llo x){
llo mi=inf;
for(auto j:cur){
mi=min(mi,val(j,x));
}
mi=min(mi,bin(x));
return mi;
}
llo aa[100001];
llo bb[100001];
llo dp[100001];
llo pre[100001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>aa[i];
}
for(llo i=0;i<n;i++){
cin>>bb[i];
}
pre[0]=bb[0];
for(llo i=1;i<n;i++){
pre[i]=pre[i-1]+bb[i];
}
dp[0]=0;
insert(-2*aa[0],dp[0]+aa[0]*aa[0]-pre[0]);
for(llo i=1;i<n;i++){
dp[i]=query(aa[i])+pre[i-1]+aa[i]*aa[i];
insert(-2*aa[i],dp[i]+aa[i]*aa[i]-pre[i]);
}
cout<<dp[n-1]<<endl;
return 0;
}
Compilation message
building.cpp:14:9: warning: overflow in implicit constant conversion [-Woverflow]
llo inf=1e19;
^~~~
building.cpp: In function 'void update()':
building.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cur.size()>bl){
~~~~~~~~~~^~~
building.cpp:34:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<cur.size() and ind2<cht.size()){
~~~^~~~~~~~~~~
building.cpp:34:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<cur.size() and ind2<cht.size()){
~~~~^~~~~~~~~~~
building.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<cur.size() ){
~~~^~~~~~~~~~~
building.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind2<cht.size() ){
~~~~^~~~~~~~~~~
building.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1;j<cht.size();j++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
4760 KB |
Output is correct |
| 2 |
Correct |
74 ms |
4712 KB |
Output is correct |
| 3 |
Correct |
70 ms |
4576 KB |
Output is correct |
| 4 |
Correct |
73 ms |
4392 KB |
Output is correct |
| 5 |
Correct |
126 ms |
5492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
71 ms |
4760 KB |
Output is correct |
| 7 |
Correct |
74 ms |
4712 KB |
Output is correct |
| 8 |
Correct |
70 ms |
4576 KB |
Output is correct |
| 9 |
Correct |
73 ms |
4392 KB |
Output is correct |
| 10 |
Correct |
126 ms |
5492 KB |
Output is correct |
| 11 |
Correct |
69 ms |
4728 KB |
Output is correct |
| 12 |
Correct |
71 ms |
4600 KB |
Output is correct |
| 13 |
Correct |
61 ms |
4604 KB |
Output is correct |
| 14 |
Correct |
72 ms |
4728 KB |
Output is correct |
| 15 |
Correct |
343 ms |
9424 KB |
Output is correct |
| 16 |
Correct |
126 ms |
5488 KB |
Output is correct |
| 17 |
Correct |
50 ms |
4600 KB |
Output is correct |
| 18 |
Incorrect |
57 ms |
4472 KB |
Output isn't correct |
