#include <bits/stdc++.h>
using namespace std;
#define taskname "CEOI17_building"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=1e5+5,H=1e6+6;
const int64_t LINF=1e18;
int n,h[N],w[N];
int64_t f[N];
struct Line
{
int64_t a,b;
};
Line st[4*H];
int64_t Get(Line d,int64_t x)
{
return d.a*x+d.b;
}
void Build(int id,int l,int r)
{
if(l==r)
{
st[id]={0,LINF};
return;
}
Build(id*2,l,(l+r)/2);
Build(id*2+1,(l+r)/2+1,r);
st[id]={0,LINF};
}
void Update(int id,int l,int r,int i,int j,Line val)
{
if(r<i||l>j)
{
return;
}
int mid=(l+r)/2;
if(i<=l&&r<=j)
{
if(Get(st[id],l)<=Get(val,l)&&Get(st[id],r)<=Get(val,r))
{
return;
}
if(Get(st[id],l)>=Get(val,l)&&Get(st[id],r)>=Get(val,r))
{
st[id]=val;
return;
}
if(Get(st[id],l)<=Get(val,l)&&Get(st[id],mid)<=Get(val,mid))
{
Update(id*2+1,l,r,i,j,val);
return;
}
if(Get(st[id],l)>=Get(val,l)&&Get(st[id],mid)>=Get(val,mid))
{
Update(id*2+1,l,r,i,j,st[id]);
st[id]=val;
return;
}
if(Get(st[id],mid+1)<=Get(val,mid+1)&&Get(st[id],r)<=Get(val,r))
{
Update(id*2,l,r,i,j,val);
return;
}
if(Get(st[id],mid+1)>=Get(val,mid+1)&&Get(st[id],r)>=Get(val,r))
{
Update(id*2,l,r,i,j,st[id]);
st[id]=val;
return;
}
return;
}
Update(id*2,l,mid,i,j,val);
Update(id*2+1,mid+1,r,i,j,val);
}
int64_t Query(int id,int l,int r,int64_t x)
{
if(r<x||l>x)
{
return LINF;
}
int64_t res=Get(st[id],x);
if(l==r)
{
return res;
}
res=min(res,Query(id*2,l,(l+r)/2,x));
res=min(res,Query(id*2+1,(l+r)/2+1,r,x));
return res;
}
void Sub1()
{
int64_t sumW=0;
forinc(i,1,n)
{
sumW+=w[i];
}
f[1]=-w[1];
forinc(i,2,n)
{
f[i]=LINF;
forinc(j,1,i-1)
{
f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
}
}
cout<<f[n]+sumW;
}
void Sub3()
{
Build(1,0,H-1);
int64_t sumW=0;
forinc(i,1,n)
{
sumW+=w[i];
}
//f[j]+h[i]^2-2*h[i]*h[j]+h[j]^2-w[i]
//f[j]-2*h[j]+h[j]^2
f[1]=-w[1];
Update(1,0,H-1,0,H-1,{(int64_t)-2*h[1],f[1]+(int64_t)h[1]*h[1]});
forinc(i,2,n)
{
f[i]=LINF;
// forinc(j,1,i-1)
// {
// f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
// }
f[i]=Query(1,0,H-1,h[i])+(int64_t)h[i]*h[i]-w[i];
Update(1,0,H-1,0,H-1,{(int64_t)-2*h[i],f[i]+(int64_t)h[i]*h[i]});
}
cout<<f[n]+sumW;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
// freopen(taskname".INP","r",stdin);
#endif // ONLINE_JUDGE
cin>>n;
forinc(i,1,n)
{
cin>>h[i];
}
forinc(i,1,n)
{
cin>>w[i];
}
Sub3();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
33144 KB |
Output is correct |
| 2 |
Runtime error |
65 ms |
67064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
69632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
33144 KB |
Output is correct |
| 2 |
Runtime error |
65 ms |
67064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
