# 2018-2019 ICPC, NEERC, Southern Subregional Contest D. Garbage Disposal

D. Garbage Disposal

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next nn days Vasya knows aiai — number of units of garbage he will produce on the ii-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to kk units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given nn days. No garbage should be left after the nn-th day.

Input

The first line of the input contains two integers nn and kk (1≤n≤2⋅105,1≤k≤1091≤n≤2⋅105,1≤k≤109) — number of days to consider and bag's capacity. The second line contains nn space separated integers aiai (0≤ai≤1090≤ai≤109) — the number of units of garbage produced on the ii-th day.

Output

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the nn-th day. In a day it is allowed to compose and drop multiple bags.

Examples

input

Copy

```3 2
3 2 1```

output

Copy

`3`

input

Copy

```5 1
1000000000 1000000000 1000000000 1000000000 1000000000```

output

Copy

`5000000000`

input

Copy

```3 2
1 0 1```

output

Copy

`2`

input

Copy

```4 4
2 8 4 1```

output

Copy

```4

```// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 300005
const double eps = 1e-6;
using namespace std;
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
ll n,k,a[maxn];
int main()
{
cin>>n>>k;
ll sum=0,temp=inf;
for(rg i=1;i<=n;i++)
{
if(temp<=k&&temp)
{
sum++;
a[i]-=k-temp;
if(a[i]<0)a[i]=0;
}
if(a[i]>=0)
{
sum+=a[i]/k;
temp=a[i]%k;
}
//cout<<temp<<" "<<sum<<" "<<a[i]<<endl;
}
cout<<sum+(temp!=0)<<endl;
return 0;
}```

0 条评论

• ### Codeforces Beta Round #14 (Div. 2)A. Letter

A boy Bob likes to draw. Not long ago he bought a rectangular graph (checked) sh...

• ### Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

You are given an unweighted tree with nn vertices. Recall that a tree is a conne...

• ### Educational Codeforces Round 81 (Rated for Div. 2) A. Display The Number

You have a large electronic screen which can display up to 998244353998244353 de...

• ### Codeforce 1102 C. Doors Breaking and Repairing

You are policeman and you are playing a game with Slavik. The game is turn-based...

• ### IT安全狂妄自大的危险

自从今年3月，随着疫情的持续蔓延，企业和组织开始实施在家办公(WFH)政策以来，企业网络安全受到的危害越来越大。

• ### 政府应该奖励合作吗？来自基于代理的财富再分配模型的见解

在我们的多智能体模型中，智能体从重复的互动中产生财富，为此假定了囚徒的困境支付矩阵。他们的收益由政府以α税率征税。由此产生的预算用于支付行政费用并向合作社代理商...

• ### 加权N元组bandit进化算法以优化游戏AI（CS AI）

N元组bandit进化算法（NTBEA）已被证明在优化游戏AI中的算法参数方面非常有效。 其潜在的弱点是在模型中使用了所有成分元组的简单平均值。 这项研究通过...

• ### 在 Octree 网格上扩展的本地时间步长（CS）

双曲偏微分方程（PDES）的数值解在科学和工程中随处可见。行法是一种在时空定义时对 PED 进行离散化的通俗方法，其中空间和时间是独立离散的。在自适应网格上使用...

• ### Top 5 Real Life Usage of Blockchain

Many businesses are embracing blockchain technology to simplify tasks in their f...