首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CodeForces 709A Juicer

CodeForces 709A Juicer

作者头像
ShenduCC
发布2018-04-27 10:52:46
9380
发布2018-04-27 10:52:46
举报
文章被收录于专栏:算法修养算法修养

A. Juicer

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input

The first line of the input contains three integers nb and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output

Print one integer — the number of times Kolya will have to empty the waste section.

Examples

input

2 7 10
5 6

output

1

input

1 5 10
7

output

0

input

3 10 10
5 7 7

output

1

input

1 1 1
1

output

0
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <math.h>

using namespace std;
int n,b,d;
int a[100005];
int main()
{
    scanf("%d%d%d",&n,&b,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int ans=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>b) continue;
        else sum+=a[i];
        if(sum>d)
            ans++,sum=0;
    }
    printf("%d\n",ans);
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-09-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档