Codeforces Round #321 (Div. 2)-B. Kefa and Company，区间最大值！

->链接在此<-

B. Kefa and Company

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 least dunits
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.

Examples

input

output

input

output

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,问所选的人的友谊值最大是多少。

很显然是一个区间最大值问题。我们来看这个前提条件，所选的人中任意两个人的金钱差值要小于d,我们便可以按金钱值从小到大排序，假设从前往后一次增大；这样所选的一些人的金钱最大差值是最后面的那个人的钱减去最前面的那个人的钱，再与d进行比较，如果差值小于d则可以选这些人，大于等于d则要舍弃最前面那个人，当然了，我们可以用第一个人来初始化当前友谊最大值，这样在往后遍历的过程中只需比较所选的连续的几个人（相当于一段区间）的友谊值总和与当前最大友谊值；看代码详解：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=100000+10;

struct node

{

    int n;

    long long v;

}a[N];

long long s[N];

int cmp(node a,node b)

{

    return a.n<b.n;//按金钱排序；

}

int main()

{

    int m,d,i,j;

    while(~scanf("%d%d",&m,&d))

    {

        memset(s,0,sizeof(s));

        for(i=0; i<m; i++)

            scanf("%d%I64d",&a[i].n,&a[i].v);

        sort(a,a+m,cmp);

        s[0]=a[0].v;

        j=0;

        long long maxx=a[0].v;//初始化当前友谊最大值；

        for(i=1; i<m; i++)

        {

            s[i]=s[i-1]+a[i].v;//将友谊值累加起来，方便计算所选某一段区间的友谊值总和；

             maxx=max(maxx,a[i].v);

            while(a[i].n-a[j].n>=d)

            {

                j++;//如果这段区间的金钱最大差大于等于d则舍弃最开始那个，可以自己手推一遍样例就理解了；

            }

            maxx=max(maxx,s[i]-s[j-1]);

        }

        printf("%I64d\n",maxx);//注意数据范围用long long；

    }

    return 0;

}

巴特西

Codeforces Round #321 (Div. 2)-B. Kefa and Company，区间最大值！

最新文章

热门文章