Codeforces Round #321 (Div. 2) B. Kefa and Company | 书脊

Codeforces Round #321 (Div. 2) B. Kefa and Company | 书脊
http://codeforces.com/contest/580/problem/B

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at leastd units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type mi,si (0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

Sample test(s)

input

4 5
75 5
0 100
150 20
75 1

output

100

input

5 100
0 7
11 32
99 10
46 8
87 54

output

111

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

题目大意: 给n,d两个整数,给n个pair<first,second>, 让你找second的合最大的pair组, 满足first之间的差值不大于d. 返回sum.

---

分析: 因为要满足的条件是pair中, first的差值不大于d, 所以首先我们要以first为基准, 排序n个pair. 其次,我们要找期中second的合最大的数组, 满足first的差不大于d, 这时, 我们已经知道, 答案在已排序的数组中, 并且是连续的子数组. 这时, 我们用双指针扫描. 第一个指针i扫整个pair组的每一个pair, 第二个指针j在i后边, 用来判断当前元素是否能满足abs(A[cur] .first �C A[i].first) < d. 如果不满足, 要往前移动j,并且把A[j]从cur中踢除.. 然后每次取最大值.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public void solve(int testNumber, InputReader in, OutputWriter out) {         int n = in.readInt();         int d = in.readInt();         Pair<Integer, Integer>[] ary = new Pair[n];         for (int i = 0; i < n; i++) {             ary[i] = Pair.makePair(in.readInt(),in.readInt());         }         Arrays.sort(ary);         long cur = 0;         int j = 0;         long max = 0;         for (int i = 0; i < ary.length; i++) {             cur += ary[i].second;             while (j < i && Math.abs(ary[i].first - ary[j].first)>=d){                 cur -= ary[j].second;                 j++;             }             max = Math.max(max, cur);         }         out.print(max);     }

Read full article from Codeforces Round #321 (Div. 2) B. Kefa and Company | 书脊