[CF]580B - Kefa and Company

[CF]580B.cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long LL;
LL sum[maxn];
struct Company{
    int money, ship;
    Company(int _m = 0, int _s = 0):money(_m),ship(_s){}

    bool operator < (const Company& c)const{
        return money < c.money;
    }
};Company cpm[maxn];

int main(){
    int n, d;
    while(scanf("%d%d", &n, &d) == 2){
        LL ans = -1e9; sum[0] = 0;
        for(int k = 0; k < n; k++){
            int m, s;
            scanf("%d%d", &m, &s);
            cpm[k] = Company(m, s);
        }
        sort(cpm, cpm + n);

        for(int i = 0; i < n; i++)
            sum[i+1] = sum[i] + cpm[i].ship;

        for(int i = 0; i < n; i++){
            int dist = lower_bound(cpm+i, cpm+n, cpm[i].money + d) - cpm - i;
            ans = max(ans, sum[dist+i]-sum[i]);
        }
        printf("%lld\n", ans);
    }
}