Hướng dẫn giải của HSG THPT Thanh Hóa 2022 - Mario
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ta thấy rằng chiến thuật đi đường tối ưu là đi sang bên trái đến một cây nấm nào đó, quay về phía bên phải rồi di chuyển xa nhất có thể (với trường hợp đi sang phải trước thì làm tương tự). Với những đoạn mà ta di chuyển qua lại, ta sẽ gọi chúng là đoạn ~[l,r]~. Ta sẽ tìm những cây nấm có tọa độ ~X_i~ nằm trong đoạn ~[l,r]~, tính tổng các giá trị ~W_i~ từ đó tìm ra đoạn mà có giá trị lớn nhất. Để tìm được những cây nấm nằm trong đoạn trên ta cần sử dụng tìm kiếm nhị phân kết hợp với mảng cộng dồn các giá trị ~W_i~ của cây nấm theo thứ tự ~X_i~ tăng dần.
Bình luận
include <bits/stdc++.h>
define ll long long
define N 10000005
define f first
define s second
using namespace std; ll n,x,k,l[N3],r[N3],s1,s2; vector<pair>trai; vector<pair>phai; ll timbenphai(ll kc){ ll l=1,r=s2,kq=-1; while(l<=r){ ll g=(l+r)/2; if(kc+2(phai[g].f-x)<=k){ kq=g; l=g+1; } else r=g-1; } return kq; } ll timbentrai(ll kc){ ll l=1,r=s1,kq=-1; while(l<=r){ ll g=(l+r)/2; if(kc+2(x-trai[g].f)<=k){ kq=g; r=g-1; } else l=g+1; } return kq; } int main() { iosbase::syncwithstdio(0); cin.tie(0); cout.tie(0); freopen("MARIO.inp","r",stdin); freopen("MARIO.out","w",stdout); cin>>n>>x>>k; ll a,b; trai.pushback({-1,-1}); phai.pushback({-1,-1}); for(ll i=1;i<=n;i++){ cin>>a>>b; if(a<x) trai.pushback({a,b}); else phai.push_back({a,b}); } s1=trai.size()-1; s2=phai.size()-1; sort(trai.begin(),trai.end()); sort(phai.begin(),phai.end()); for(ll i=1;i<=s1;i++) l[i]=l[i-1]+trai[i].s; for(ll i=1;i<=s2;i++) r[i]=r[i-1]+phai[i].s; ll max1=0,max2=0; for(ll i=1;i<=s1;i++){ ll kc=x-trai[i].f; ll b=0; if(kc>k) continue; else{ b=l[s1]-l[i-1]; ll vt=timbenphai(kc); if(vt!=-1) b=b+r[vt]; max1=max(max1,b); } cout<<b<<" "; } cout<<endl; for(ll i=1;i<=s2;i++){ ll kc=phai[i].f-x; ll b=0; if(kc>k) break; else{ b=r[i]; ll vt=timbentrai(kc); if(vt!=-1) b=b+l[s1]-l[vt-1]; max2=max(max2,b); } cout<<b<<" "; } cout<<endl; cout<<max(max1,max2); return 0; }</pair></pair>