#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#define fi first
#define se second
#define forl(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
typedef pair<long double,int> ldi;
ll n,h[100005],w[100005],gt[100005];
int sh=0;
//sub2
map<int,ii> line;
ll cal(int num_line,ll x)
{
return 1LL*line[num_line].first*x + line[num_line].second;
// tính y=ax+b;
}
ll giao_diem(int nline1,int nline2,bool isright)
{
ll a=line[nline1].second-line[nline2].second;
ll b=line[nline2].first-line[nline1].first;
if(b==0)return 999999999999999;
if((a%b)==0)return (a)/(b)+1;
if(isright) return (a)/(b)+1;// a<0
return (a)/(b)+1;
}
/**/
set<iii> s;// hệ số góc , biên trái, số hiệu
set<ii> s2;// biên trái, số hiệu
bool important(int sh,ll left,set<iii>::iterator it)
{
if(it==s.begin())return true;
it--;
iii num=*it;
if(left>giao_diem(sh,num.second,0))return false;//ko quan trọng
return true;
}
void insert_line(ll a,ll b)
{
sh++;
line[sh]=ii(a,b);
set<iii>::iterator it=s.begin();
ll left=-999999999999999;
//cout<<"insert y="<<a<<"x + "<<b<<endl;
while(true)
{
if(s.empty())break;
it = s.lower_bound(iii(ii(a,-999999999999999),-1));
if(it==s.end()){break;}
iii num=*it;
int nline=num.second;
//cout<<"line:"<<nline<<endl;
left=giao_diem(sh,nline,0);//giao điểm của đt hiện tại và đt *it
//cout<<sh<<": left="<<left<<endl;
//song song
if(left==999999999999999)
{
if(a>0)
{
//cout<<"C1"<<endl;
if(b>line[nline].second){left=num.first.second;s.erase(it);s2.erase(ii(num.first.second,num.second));}
else return;
}
else
{
//cout<<"C2"<<endl;
if(b<line[nline].second){left=num.first.second;s.erase(it);s2.erase(ii(num.first.second,num.second));}
else return;
}
}
else
{
if(!important(sh,left,it)){return;}//cout<<"ko push"<<endl;
if(left<=num.first.second){left=num.first.second;s.erase(it);s2.erase(ii(num.first.second,num.second));}
else break;
}
}
//cout<<sh<<" Ok1"<<endl;
if(s.size()>=1 && it!=s.begin())
{
//cout<<"Continue:"<<endl;
it--;
iii tam=*it;
//cout<<"Bỏ đường thẳng số "<<tam.second<<endl;
s.erase(it);
s2.erase(ii( tam.first.second, tam.second));
s.insert(iii( ii(tam.first.first, giao_diem(sh,tam.second,1)) , tam.second));
s2.insert(ii( giao_diem(sh,tam.second,1) , tam.second ));
}
s.insert(iii( ii(a,left),sh));
s2.insert(ii(left,sh));
//cout<<"list đoạn thẳng"<<endl;
//for(auto it:s)cout<<it.first.first<<" "<<it.first.second<<" "<<it.second<<endl;
//cout<<"end_________________________________________"<<endl;
}
ll query(int x)
{
set<ii>::iterator it=s2.lower_bound(ii(x,0));
ii tam=*it;
ll ans=cal(tam.second,x);
if(it==s2.begin())return ans;
it--;
tam=*it;
it++;it++;
ans=min(ans,cal(tam.second,x));
if(it==s2.end())return ans;
tam=*it;
ans=min(ans,cal(tam.second,x));
return ans;
//cout<<x<<" -> thuộc đoạn y="<<line[tam.second].first<<"x + "<<line[tam.second].second<<endl;
}
//sub1
ll cost(int from,int to)
{
return (w[to-1]-w[from]);
}
void sub1()
{
ll dp[n+5];
dp[1]=0;
forl(i,2,n)
{
dp[i]=1e15;
forl(j,1,i-1)
{
dp[i]=min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j])+cost(j,i));
// cout<<i<<" "<<j<<": "<<dp[j]<<" "<<(h[i]-h[j])*(h[i]-h[j])<<" "<<cost(j,i)<<endl;
// cout<<"-> "<<dp[j]+(h[i]-h[j])*(h[i]-h[j])+cost(j,i)<<endl;
}
}
cout<<dp[n];
//forl(i,1,n)cout<<dp[i]<<" ";cout<<endl;
}
void sub2()
{
ll dp[n+5];dp[1]=0;//dp[2]=(h[2]-h[1])*(h[2]-h[1]);
// chi phí xây từ 1 -> i
// = (h[i]-h[j])^2 - w[i] - w[j] + dp[j]
// = hi^2 - 2*hi*hj + hj^2 - wi - wj +dp[j]
// = (-2*hj) * hi + (hj^2-wj+dp[j]) + hi^2 - wi
// a * x + b + CONST
insert_line( -2*h[1] , h[1]*h[1] +dp[1] );
//cout<<0<<" ";
forl(i,2,n)
{
// cout<<i<<"__________\n ";
//cout<<i<<": list đoạn thẳng"<<endl;
//for(auto it:s2){cout<<it.first<<" -> numline="<<it.second<<": ";
//cout<<line[it.second].first<<"x + "<<line[it.second].second<<endl;}
//cout<<endl;
dp[i]=query(h[i]) + h[i]*h[i] - gt[i];
//cout<<"dp["<<i<<"]= "<<dp[i]+w[i]<<" <>\n";
insert_line(-2*h[i], h[i]*h[i]+dp[i]);
}
cout<<dp[n]+w[n]-gt[1]-gt[n];
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("xaycau.inp","r",stdin);
// freopen("xaycau.out","w",stdout);
#endif // ONLINE_JUDGE
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
w[0]=0;
forl(i,1,n)cin>>h[i];
forl(i,1,n){cin>>gt[i];if(i==1 || i==n)gt[i]=0;}
forl(i,1,n){w[i]=w[i-1]+gt[i];}
// forl(i,1,n)cout<<w[i]<<" ";cout<<endl;
// cout<<cost(3,5)<<endl;
if(n<=2000)sub1();else sub2();
//sub1();cout<<endl;sub2();cout<<endl;
/*insert_line(0,4);
insert_line(-3,12);
insert_line(0,2);
insert_line(2,1);
insert_line(-3,2);
cout<<"list đoạn thẳng"<<endl;
for(auto it:s2)cout<<it.first<<" "<<it.second<<endl;
cout<<"QUERY:"<<endl;
forl(i,-3,5)cout<<i<<": "<<query(i)<<endl;*/
//cout<<"list đoạn thẳng"<<endl;
//(auto it:s2)cout<<it.first<<" -> "<<it.second<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
9936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
356 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Incorrect |
387 ms |
9936 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
