This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long inf = 2e18;
struct line{
long long m;
long long c;
double val(double x){
return m*x+c;
}
int left=-1;
int right=-1;
};
struct liChaoTree{
line *st;
line def;
int cr = 0;
liChaoTree(int nodes){
def.m=0;
def.c=LLONG_MAX;
st=new line[nodes];
fill(st,st+nodes,def);
}
void addLine(line lin, long long l=0, long long r=1e9+5, int ind=0){
long long mid = (l+r)/2;
if(st[ind].val(l)<=lin.val(l)&&st[ind].val(r)<=lin.val(r)){
return;
}
lin.left=st[ind].left;
lin.right=st[ind].right;
if(st[ind].val(mid)>lin.val(mid)){
swap(lin,st[ind]);
}
if(l==r)
return;
else if(st[ind].val(l)>lin.val(l)){
if(lin.left==-1){
cr++;
st[ind].left=cr;
}
addLine(lin,l,mid,st[ind].left);
}
else{
if(lin.right==-1){
cr++;
st[ind].right=cr;
}
addLine(lin,mid+1,r,st[ind].right);
}
}
double query(long long x, long long l=0, long long r=1e9+5, int ind=0){
if(l==r&&r==x){
return st[ind].val(x);
}
if(x<l||x>r){
return def.val(x);
}
long long mid = (l+r)/2;
double ans1 = 2e18;
if(st[ind].left!=-1){
ans1=query(x,l,mid,st[ind].left);
}
double ans2 = 2e18;
if(st[ind].right!=-1){
ans2=query(x,mid+1,r,st[ind].right);
}
return min({st[ind].val(x),ans1,ans2});
}
};
signed main(){
//ios::sync_with_stdio(0);
//cin.tie(0);
long long n;
cin >> n;
long long arr[n];
for(long long &i : arr){
cin >> i;
}
long long w[n];
for(long long &i : w){
cin >> i;
}
long long dp[n];
dp[0]=0;
dp[1]=arr[0]*arr[0]+arr[1]*arr[1]-2*arr[0]*arr[1];
long long pref[n];
pref[0]=w[0];
for(int i = 1;i<n;i++){
pref[i]=pref[i-1]+w[i];
}
liChaoTree lct(2e7);
line l1,l2;
l1.m=-2*arr[0];
l2.m=-2*arr[1];
l1.c=dp[0]-pref[0]+arr[0]*arr[0];
l2.c=dp[1]-pref[1]+arr[1]*arr[1];
//cout << "adding: \n";
lct.addLine(l1);
lct.addLine(l2);
for(long long i = 2;i<n;i++){
dp[i]=inf;
//cout << dp[i] << " " << lct.query(arr[i]) << "\n";
dp[i]=lct.query(arr[i]);
dp[i]+=pref[i-1]+arr[i]*arr[i];
line t;
t.m=-2*arr[i];
t.c=dp[i]-pref[i]+arr[i]*arr[i];
lct.addLine(t);
}
cout << dp[n-1];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |