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;
const long long N=1024*1024,inf=N*N*N;
long long n,i,sum;
long long s[N],h[N];
pair <long long,long long> tree[2*N];
long long val(pair <long long,long long> line,long long x) {
return x*line.first+line.second;
}
long long solve(long long x) {
long long pos=x+N,ret=inf;
while (pos) {
ret=min(ret,val(tree[pos],x));
pos/=2;
}
return ret;
}
void add_line(pair <long long,long long> line,long long p,long long l,long long r) {
long long m=(l+r)/2;
bool lef=val(line,l-N)<val(tree[p],l-N);
bool mid=val(line,m-N)<val(tree[p],m-N);
if (mid)
swap(tree[p],line);
if (p<N) {
if (lef!=mid)
add_line(line,2*p,l,m);
else
add_line(line,2*p+1,m,r);
}
return;
}
int main() {
cin>>n;
for (i=1;i<=n;i++)
cin>>h[i];
for (i=1;i<=n;i++) {
cin>>s[i];
sum+=s[i];
}
for (i=1;i<(2*N);i++)
tree[i]={-2*h[1],h[1]*h[1]-s[1]};
for (i=2;i<n;i++)
add_line({-2*h[i],2*h[i]*h[i]-s[i]+solve(h[i])},1,N,2*N);
cout<<solve(h[n])+sum+h[n]*h[n]-s[n]<<endl;
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... |