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;
typedef long long ll;
typedef long double ld;
const ll inf=(1ll<<60);
struct line
{
ll k,n;
mutable ll r;
line(ll a,ll b,ll c){k=a;n=b;r=c;}
};
bool operator<(const line &a,const line &b){return a.k>b.k;}
bool operator<(const line &a,const ll &b){return a.r<b;}
ld intersect(line a,line b){return (((ld)b.n-a.n)/(a.k-b.k));}
struct cht
{
set<line,less<>> s;
void upd(set<line>::iterator it,ll nr){it->r=nr;}
void add(ll k,ll n)
{
line now(k,n,0);
auto it=s.lower_bound(now);
if(it!=s.end()&&it->k==k)
{
if(it->n>n) it=s.erase(it);
else return;
}
if(it!=s.end()&&it!=s.begin()&&intersect(*prev(it),now)>intersect(now,*it)) return;
s.insert(now);
while(it!=s.end()&&next(it)!=s.end()&&intersect(now,*it)>intersect(*it,*next(it))) it=s.erase(it);
it--;
while(it!=s.begin()&&prev(it)!=s.begin()&&intersect(now,*prev(it))<intersect(*prev(it),*prev(prev(it)))) s.erase(prev(it));
if(it!=s.begin()) upd(prev(it),floor(intersect(*prev(it),*it)));
if(next(it)!=s.end()) upd(it,floor(intersect(*it,*next(it))));
else upd(it,inf);
}
ll query(ll a)
{
line best=*s.lower_bound(a);
return (best.k*a+best.n);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<ll> h(n+1,0);
for(int i=1;i<=n;i++) cin >> h[i];
vector<ll> w(n+1,0);
for(int i=1;i<=n;i++) cin >> w[i];
vector<ll> sum(n+1,0);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
cht c;
c.add(-2*h[1],h[1]*h[1]-w[1]);
for(int i=2;i<=n;i++)
{
ll dp=h[i]*h[i]+sum[i-1]+c.query(h[i]);
c.add(-2*h[i],dp+h[i]*h[i]-sum[i]);
if(i==n) cout << dp << "\n";
}
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... |