VLN - Vải Lục Ngạn

no tags 

Nhân dịp đến quê hương Bắc Giang tham gia thi chọn học sinh giỏi Trại hè Hùng Vương, Hà đến thăm trang trại trồng vải thiều của bác Thuấn. Trang trại gồm n cây thẳng hàng và cách đều nhau (khoảng cách từ gốc cây i đến gốc cây i+1 là 3 mét với mọi i = 1, 2, 3, ..., n-1).

Năm nay là năm được mùa nên cây nào cũng sai quả, cây thứ i có số lượng quả vải là ai quả. Bác Thuấn rất lo lắng vì tuổi già rồi làm sao có thể hái được hết số vải thiều này, Hà đang nghĩ cách giúp bác Thuấn thì đột nhiên có một ông tiên hiện ra trước mắt Hà và nói: “Ta cho cháu một chiếc túi thần, cháu hãy chọn một chỗ đứng ở một gốc cây trong n cây rồi hô to câu thần chú [Vải ơi chui vào đây], khi đó tất cả quả ở các cây có khoảng cách tính từ gốc đến chỗ cháu đứng không vượt quá H sẽ từ từ rời khỏi cành và bay vào túi thần này.”

Yêu cầu

Hãy cho biết Hà có thể thu hoạch giúp bác Thuấn được tối đa bao nhiêu quả vải nếu lời nói của ông tiên là hiện thực.

Input

Đầu vào có dạng

  • Dòng đầu chứa hai số nguyên dương n, H (n ≤ 100; H ≤ 109)
  • Dòng thứ hai chứa n số nguyên a, a2 , . . ., an trong đó ai (ai ≤ 109 ; i = 1, 2, 3, . . ., n) là số lượng quả của cây vải thứ i.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Gồm một số nguyên duy nhất là tổng số lượng quả vải nhiều nhất mà Hà có thể thu hoạch giúp bác Thuấn.

Ví dụ

Input:
5 3
1 2 2 2 1 Output: 6

hide comments
pjotrek2626_: 2023-03-01 11:13:58

Nhân dịp đến quê hương Bắc Giang tham gia thi chọn học sinh giỏi Trại hè Hùng Vương, Hà đến thăm trang trại trồng vải thiều của bác Thuấn. Trang trại gồm n cây thẳng hàng và cách đều nhau (khoảng cách từ gốc cây i đến gốc cây i+1 là 3 mét với mọi i = 1, 2, 3, ..., n-1).

nguyen_tuan2: 2019-03-24 09:51:35

In the garden, there are "N" trees (1,2,3....N, it is planted in a row). The distance between 2 trees is 3 meter. There are "A" fruit per tree. ( a1, a2, ....aN, it is entered from keyboard). "H" is a constant, it is entered from keyboard. If you stand at a root and say a mantra, all of fruit in trees which have distance to your place shorter than H will fall down. find the maximum number of fruit you can harvest.

input
* first line include N, H (N<= 100, H<= 10^9)
*second line include: a1,a2,.....aN (a < 10^9)
output
* is the maximum number of fruit that you can harvest

example:

input
5 3
1 2 2 2 1

output
6

ductri179: 2018-10-27 11:42:18

@guptaishwar this is a problem written by Vietnamese, why are you interested in this problem cus I'm really curious

guptaishwar: 2018-07-06 18:04:01

Can someone translate it in english


Added by:CAdmin
Date:2017-10-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Trại hè Hùng Vương 2015