Submission #477396

#TimeUsernameProblemLanguageResultExecution timeMemory
477396llcdBuilding Bridges (CEOI17_building)C++17
100 / 100
121 ms12728 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...