TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3635
  • 题目
  • P3635卖甘蔗
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板在菜市场卖甘蔗。他有一根很长的甘蔗,该甘蔗总共有n个小节构成,卖甘蔗是以节为单位,切割时只会从节与节的连接处切开。下图是一段长度为4的甘蔗,由4小节构成。

    为方便顾客,何老板事先测量出了每一节甘蔗的含糖量。今天来了一个古怪的顾客,他要求购买一段甘蔗,他对甘蔗的长度没有限制,但是要求这段甘蔗的含糖量的平均值要大于m,也就是说,如果选了一段长度为k的甘蔗,那么顾客要求这k节甘蔗的含糖量之和的平均值要超过m。
    何老板想知道,总用有多少种方案可以满足这位顾客的要求,请你帮他算一算。
    例如,有一根长度为4的甘蔗,每一节的含糖量分别为3、6、2、5,顾客要求一段含糖量平均值超过4的甘蔗,我们如下4种可行的方案:
    [6] 含糖量平均值为6
    [5] 含糖量平均值为5
    [3 6] 含糖量平均值为4.5
    [6 2 5] 含糖量平均值为4.33...

    输入格式

    第一行,两个整数n和m。
    第二行,n个空格间隔的整数,表示每一节甘蔗的含糖量

    输出格式

    一行,一个整数,表示方案数

    样例输入

    输入样例1
    4 3
    3 7 2 4

    输入样例2
    4 4
    3 6 2 5

    输入样例3
    10 32
    25 5 47 38 37 37 5 22 10 12 

    样例输出

    输出样例1
    7

    输出样例2
    4

    输出样例2
    12

    提示

    对于30%的数据 1 ≤ n ≤ 1000
    对于100%的数据 1 ≤ n ≤ 100000, 0 ≤ m ≤ 10000 , 0 ≤ 含糖量 ≤ 10000


    来源  感谢QXY同学提供题目、数据、标程