Đề bài: $\href{https://codeforces.com/contest/580/problem/B}{Đây}$
Tóm tắt: Cho $n$ cặp $(a_i,b_i)$ và một số $d$. Hãy chọn ra một tập con (rời rạc) sao không không tồn tại hai chỉ số $i,j$ thỏa mãn $abs(a_i-a_j)<d$ và $\sum(b_i)$ là lớn nhất.
Lời giải:
+ Sort $n$ cặp trên theo thứ tự tăng dần. Sao đó dùng 2 con trỏ, tìm đoạn con liên tiếp thỏa mãn yêu cầu bài toán trên.
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define N 100005
- #define F first
- #define S second
- pair<int,int> a[N];
- long long o,res=-1;
- int i,j,l,r,n,m;
- int main(){
- // freopen("input.inp","r",stdin);
- // freopen("output.out","w",stdout);
- cin>>n>>m;
- for(i=0;i<n;++i){
- scanf("%d%d",&a[i].F,&a[i].S);
- }
- sort(a,a+n);
- for(l=0;l<n;o-=a[l].S,++l){
- while(r<n && abs(a[l].F-a[r].F)<m)o+=a[r].S,++r;
- if(o>=res) res=o;
- }
- cout<<res<<"\n";
- }
Không có nhận xét nào:
Đăng nhận xét