oj.uz

Submission #477396

# Submission time Handle Problem Language Result Execution time Memory
477396 2021-10-02T02:18:30 Z llcd Building Bridges (CEOI17_building) C++17
100 / 100
 121 ms 12728 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3472 KB Output is correct
2 Correct 86 ms 3512 KB Output is correct
3 Correct 87 ms 3524 KB Output is correct
4 Correct 83 ms 3544 KB Output is correct
5 Correct 82 ms 5188 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 86 ms 3472 KB Output is correct
7 Correct 86 ms 3512 KB Output is correct
8 Correct 87 ms 3524 KB Output is correct
9 Correct 83 ms 3544 KB Output is correct
10 Correct 82 ms 5188 KB Output is correct
11 Correct 74 ms 3404 KB Output is correct
12 Correct 89 ms 3464 KB Output is correct
13 Correct 56 ms 3408 KB Output is correct
14 Correct 81 ms 3524 KB Output is correct
15 Correct 121 ms 12728 KB Output is correct
16 Correct 78 ms 5188 KB Output is correct
17 Correct 25 ms 3404 KB Output is correct
18 Correct 26 ms 3372 KB Output is correct