Submission #477385

#	Time	Username	Problem	Language	Result	Execution time	Memory
477385		llcd	Building Bridges (CEOI17_building)	C++17	0 / 100	3 ms	332 KiB

building

#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;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen("xaycau.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen("xaycau.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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