3673: 牛牛的灯笼(第五轮03)
题目描述
国庆长假，牛牛带着牛妹一起去逛街，他们来到一个街道，街道上从左至右悬挂 了N盏五颜六色的灯笼。
牛牛想要带牛妹去这个街道中的一小段街区看灯笼，具体来讲，牛牛会先选择街 道中的两个端点(u, v), u, v ∈ [1, N]，然后他们从街道从左往右数的第u个灯笼看到 从左往右数的第v个灯笼。
牛妹对于灯笼的喜好不同，她给这N盏灯笼都给出了一个喜爱度，第i盏灯笼的喜 爱度为likei 。
牛妹觉得好不容易出来玩，如果逛的灯笼都不太喜欢，甚至讨厌，就很难受。
具体来讲， 如果他们所逛的这一小段街区中所有灯笼的喜爱度之和小于X，牛妹 就不能接受。
牛牛不希望看到灯笼的种类数多于M，因为这样他会看的眼花。
对于第i盏灯笼和第j盏灯笼， 如果牛妹给出的喜爱度likei = likej ， 我们就认为第 i盏灯笼和第j盏灯笼是同一种灯笼。
现在牛牛想要知道，街道中有多少种选择街区的方式可以满足他们两个人的条件？
输入
第一行输入三个整数N, M, X。
接下来一行输入N个整数likei，表示每盏灯笼的喜爱度。
输出
仅一个整数，表示牛牛选择街区的方案数。
样例输入 复制
5 5 5
3 2 -4 2 3样例输出 复制
6提示
【样例 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
【样例 2 说明】
排除法， 总共 5×5 种方案， 除了(1,5),(5,1){(1,5),(5,1)}(1,5),(5,1)出现了 5 种灯笼不 满足条件，其他都是合法的。
所以答案为 5×5−2=23
【数据范围】
对于 30%的测试数据，保证1 ≤ N ≤ 10^3 。
对于不属于前 30%的另 10%的测试数据，保证M = N。
对于不属于前 30%的另 10%的测试数据，保证X = −10^9 。
对于不属于前 30%的另 10%的测试数据，保证likei ≥ 0。
对于 100%的测试数据，保证1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5, −10^9 ≤ X ≤ 10^9, −10^4 ≤ likei ≤ 10^4 。