4002. 灯笼

【题目背景】

在此键入。

【题目描述】

元宵佳节，牛牛带着牛妹一起去逛街，他们来到一个街道，街道上从左至右悬挂了N盏五颜六色的灯笼。

牛牛想要带牛妹去这个街道中的一小段街区看灯笼，具体来讲，牛牛会先选择街道中的两个端点(u, v), u, v ∈ [1,N]，然后他们从街道从左往右数的第u个灯笼看到从左往右数的第v个灯笼。

牛妹对于灯笼的喜好不同，她给这N盏灯笼都给出了一个喜爱度，第i盏灯笼的喜爱度为like_i。

牛妹觉得好不容易出来玩，如果逛的灯笼都不太喜欢，甚至讨厌，就很难受。

具体来讲，如果他们所逛的这一小段街区中所有灯笼的喜爱度之和小于X，牛妹就不能接受。

牛牛不希望看到灯笼的种类数多于M，因为这样他会看的眼花。

对于第i盏灯笼和第j盏灯笼，如果牛妹给出的喜爱度like_i = like_j ，我们就认为第i盏灯笼和第j盏灯笼是同一种灯笼。

现在牛牛想要知道，街道中有多少种选择街区的方式可以满足他们两个人的条件？

【输入格式】

第一行输入三个整数N, M, X。

接下来一行输入N个整数like_i，表示每盏灯笼的喜爱度。

【输出格式】

仅一个整数，表示牛牛选择街区的方案数。

【样例1输入】

5 5 5
3 2 -4 2 3

【样例1输出】

6

【样例1说明】

合法的逛街方案可以是(1,2),(2,1),(4,5)(5,4),(1,5),(5,1)，一共 6 种。

【样例2输入】

5 4 -1000000000
1 2 3 4 5

【样例2输出】

23

排除法，总共 5×5 种方案，除了(1,5),(5,1){(1,5),(5,1)}(1,5),(5,1)出现了 5 种灯笼不满足条件，其他都是合法的。 所以答案为 5×5−2=23

【数据规模与约定】

30%的测试数据，保证1 ≤ N ≤ 10^3。

另 10%的测试数据，保证M = N。

另 10%的测试数据，保证X = −10^9。

另 10%的测试数据，保证like_i ≥ 0。

100%的测试数据，保证1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5, −10^9 ≤ X ≤ 10^9, −10^4 ≤like_i ≤ 10^4

【来源】

在此键入。