#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#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 long double ld;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
typedef pair<long double,int> ldi;
ll n,h[100005],w[100005],gt[100005];
struct Line
{
char loai;
ld k;//giao điểm
long long a,b; // y=ax+b;
};
set<Line> s;
typedef set<Line>::iterator s_it;
bool operator< (Line L1, Line L2)
{
if(L1.loai + L2.loai >0)return L1.k<L2.k;
else return L1.a>L2.a;
}
bool has_prev(s_it it){ return it!=s.begin(); } //ko phải phần tử đầu
bool has_next(s_it it){ return it!=s.end() && next(it)!=s.end(); } // ko phải phần tử cuối
//sub2
ld giao_diem(s_it it1, s_it it2)
{
ll a1= it1 -> a;
ll a2= it2 -> a;
ll b1= it1 -> b;
ll b2= it2 -> b;
return (ld)(b1-b2)/(a2-a1);
}
void re_cal_left(s_it it) //tính lại biên của phần tử trước phần tử dc thêm vào
{
if(has_prev(it))
{
Line L = *it;
L.k = giao_diem( prev(it) , it );
s.insert( s.erase(it) , L );
}
}
bool ko_lien_quan(s_it it)
{
if( has_next(it) && next(it)->b <= it -> b) return true;
return ( has_next(it) && has_prev(it) && giao_diem(prev(it) , next(it))<=giao_diem(prev( it),it) );
}
/**/
void insert_line(ll a,ll b)
{
s_it it;
//xử lý song song, trùng nhau
it= s.lower_bound({0,0,a,b});
if( it != s.end() && it->a==a)
{
if(it -> b <= b)return;
else s.erase(it);
}
// xóa các đoạn ko liên quan tới hull
it = s.insert({0,0,a,b}).first;
if(ko_lien_quan(it)){ s.erase(it);return; }
while(has_prev(it) && ko_lien_quan(prev(it)) )s.erase(prev(it));
while(has_next(it) && ko_lien_quan(next(it)) )s.erase(next(it));
// tính lại giao điểm sau khi insert
if( has_next(it) )re_cal_left(next(it));
re_cal_left(it);
}
ll query(ll x)
{
s_it it=s.upper_bound((Line){1,(ld)x,0,0});
it--;
return 1LL * (it->a)*x + (it->b);
}
//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()
{
// 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
ll dp[n+5];dp[1]=0;
forl(i,2,n)
{
insert_line(-2*h[i-1] , dp[i-1] + h[i-1]*h[i-1]);
ll kq=query(h[i]);
dp[i]=kq + h[i]*h[i] - gt[i];
}
cout<<dp[n]+w[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];}
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;
sub2();
/*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;
//for(auto it:s2)cout<<it.first<<" -> "<<it.second<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
90 ms |
3484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
