Submission #477396

#	Time	Username	Problem	Language	Result	Execution time	Memory
477396		llcd	Building Bridges (CEOI17_building)	C++17	100 / 100	121 ms	12728 KiB

building

#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)
{
    auto it=s.upper_bound( (Line){1,(ld)x,0,0} );
    it--;
    return it->b + x*it->a;
}

//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],sum=0;dp[1]=-gt[1];
    forl(i,1,n)sum+=gt[i];
    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]=h[i]*h[i] - gt[i] + kq;
    }
    cout<<dp[n]+sum;
}
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;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40