为了固定S**p*鸽鸽,whx和zzt来到鸽具商店选购鸽子固定器。

鸽具商店有 

n

 个不同大小的固定器,现在可以选择至多 

m

 个来固定S**p*鸽鸽。每个固定器有大小 

si

 和牢固程度 

vi

如果他们选购的固定器大小不一或是不牢固,固定S**p*鸽鸽的时候肯定会很头疼,所以定义选择的物品总牢固程度和的 

dv

 次方减大小极差的 

ds

 次方为这个方案的价值,求不同选购方案中,价值的最大值。

鸽子

输入格式

第一行四个正整数 

n,m,ds,dv

接下来 

n

 行,每行两个正整数 

si,vi

,表示第 

i

 个固定器的大小和牢固程度。

输出格式

输出一行,包含一个整数,表示价值的最大值。

样例一

input

output

样例二

input

output

样例三

见样例数据下载。

限制与约定

子任务 分值

n

 的规模

m

 的规模

ds,dv

 的规模

si,vi

 的规模

其他约定
1 5

1n10

 

1mmin(50,n)

 

ds=dv=2

 

1si,vi107

 

2 5

1n1000

 

3 10

1n2×105

 

ds=dv=1

 

4 25

ds=dv=2

 

si,vi

分别在某个范围内均匀随机生成

5 25

ds=1,dv=2

 

6 30

1ds,dv2

 

时间限制

2s

 

空间限制

考虑枚举每个右端点 然后可以用一个堆维护区间最小值 然后当我们发现我们如果把枚举的右端点都弹出的时候一定break因为剩下的我们可以简单通过左移右端点使得答案变成更优的

另外我们可以用一个链表维护如果这个节点在这次i加入的时候并没有被加入那么说明之后我再被加入的时候一定不会被加入 因为我右端点在右移 所以说我至少应该已经有了m个满足条件的点我继续使用那满足条件的m个点即可

 

分类: STL模拟

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论