Informatica Online Judge

  상자와 사탕 [1707 / 06AB]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 19   Total Tried : 20


The Champion of this Problem (C++) : gs16109 - 0ms / 111byte
My Best Submission (C++) : N/A

[Atcoder]

Background

각 상자에 ai 개의 사탕이 들어 있는 N개의 박스가 일렬로 늘어져 있다. 경곽이는 다음의 작업과 목적을 가지고 몇 번의 작업을 수행할 수 있다.

작업: 적어도 하나의 사탕을 포함하고 있는 박스를 선택하여 그 중 1개의 사탕을 먹을 수 있다.
목표: 어떤 이웃하는 두 박스의 사탕의 총 합은 최대 x개이다.


경곽이가 이러한 목표를 달성하기 위한 최소 작업의 횟수를 구해 너무 많은 사탕을 먹지 않도록 도와주자.

Input

첫 줄에 박스의 수를 나타내는 정수 N과 목표 값인 x가 입력이 된다.
두 번째 줄에 각 박스의 사탕의 수를 나타내는 값 ai가 N개 입력이 된다.

[입력값의 정의역]
2<= N <= 100,000
0 <= ai <= 1,000,000,000
0 <= x <= 1,000,000,000

Output

목표를 달성하기 위한 최소 작업의 회수를 한줄로 출력한다.

IO Example

입력1
3 3
2 2 2

출력1
1

입력
2 0
5 5

출력2
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]