#P7227. [2023省队模拟]称量

    ID: 7061 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-等价类划分0/1 背包前后缀状态分解消除被支配候选复制数组处理环单调队列

[2023省队模拟]称量

题目描述

XD 有一个秤。若放在秤上的物品的总重量小于 k⋅ck\cdot c,秤显示总重量除以 cc 后向下取整的结果。若总重量至少为 k⋅ck\cdot c,秤只显示 orz。

有 nn 个物品,第 ii 个物品重 aia_i。XD 可以任意选择一些物品放到秤上,也可以不放任何物品。问有多少对 (i,j)(i,j) 满足 1≤i<j≤n1\le i<j\le n,使得 XD 能通过这个秤确定其中哪个物品更重。

XD 知道秤的规则,但不知道每个物品的重量,也不知道这些重量为整数。他认为重量可以是实数。

输入格式

第一行三个整数 n,k,cn,k,c。

第二行 nn 个整数 aia_i,表示各个物品的重量。

输出格式

输出一行一个整数,表示答案。

样例输入

4 4 6
8 9 10 11

样例输出

4

数据范围与约定

所有输入均为正整数,且 n≤1000n\le1000,k≤1000k\le1000,c≤5000c\le5000,ai≤k⋅ca_i\le k\cdot c。

子任务 数据范围 分值
1 n≤20n\le20 20
2 n,c≤100n,c\le100
3 c≤100c\le100 30
4 无特殊限制