QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+7]
Statistics

数轴上有 n 个黑点,坐标为 a[]n 个白点,坐标为 b[](下标均从 0 开始)。同时你有两个参数 lalb,满足 n21lb<la。注意同一个位置可能有多个点。

你需要找到一个 0n1 的排列 p[],满足对于所有 i,有 a[i]b[p[i]]a[i]+la。你需要最大化满足 b[p[i]]a[i]+lb 的下标 i 的个数。数据保证存在一个合法的排列。

输入格式

第一行,三个正整数 nlalb

接下来一行,n 个正整数,表示 a[]

接下来一行,n 个正整数,表示 b[]

输出格式

输出一行一个非负整数,表示满足条件的下标个数。

样例数据

样例输入

3 5 1
1 2 5
4 6 7

样例输出

1

样例解释

n=3la=5lb=1

a[]={1,2,5}

b[]={4,6,7}

一种最好的排列是 p[]={0,2,1}b[p[2]]=b[1]=6a[2]=5 的差不超过 lb=1,其他均不满足这个条件,答案为 1

p[]={2,0,1} 不是合法的排列,因为 b[2]=7a[0]=1 匹配,它们的差为 6,超过了 la=5

p[]={1,2,0} 不是合法的排列,因为 b[0]=4a[2]=5 匹配,但不满足 b[0]a[2]

p[]={0,1,2} 虽然是合法的排列,但是答案为 0,不是最优解。

子任务

子任务 1(4 分):满足 n10

子任务 2(14 分):满足 n100

子任务 3(37 分):满足 n5000

子任务 4(16 分):满足 la=5×105

子任务 5(29 分):无特殊限制。

对于所有数据,2n5×1051a[i],b[i]5×1051lbla5×105。保证存在一个合法的排列。