GukiZ và những chồng hộp

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Có $n$ chồng hộp được xếp thành một hàng từ trái sang phải. Chồng thứ $i$ chứa $a_{i}$ hộp. Cần dọn sạch tất cả các hộp bằng $m$ học sinh làm việc đồng thời.

Tại thời điểm $0$ , tất cả học sinh đứng ngay bên trái chồng đầu tiên. Mỗi học sinh mất đúng $1$ giây để di chuyển từ vị trí ban đầu đến chồng số $1$ . Sau đó, ở mỗi giây kế tiếp, mỗi học sinh có thể thực hiện một trong hai thao tác (mỗi thao tác mất đúng $1$ giây):

Nếu đang ở chồng $i$ và $i \neq n$ , di chuyển sang chồng $i + 1$ .
Nếu chồng hiện tại còn hộp, lấy đi $1$ hộp khỏi chồng đó.

Các học sinh hoạt động hoàn toàn độc lập và có thể cùng đứng trên một chồng. Hãy tìm thời gian tối thiểu $t$ (tính bằng giây) để dọn sạch toàn bộ các hộp. Sau $t$ giây, các học sinh được phép đứng ở vị trí bất kỳ.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Một số nguyên duy nhất — thời gian tối thiểu cần thiết để dọn hết các hộp.

Ràng buộc

$1 \leq n, m \leq 10^{5}$
$0 \leq a_{i} \leq 10^{9}$
Đảm bảo có ít nhất một chồng khác rỗng.

Ví dụ

Input	Output	Giải thích
2 1 1 1	4	$1$ học sinh: di chuyển đến chồng $1$ ( $1$ s), lấy hộp ở chồng $1$ ( $1$ s), di chuyển sang chồng $2$ ( $1$ s), lấy hộp ở chồng $2$ ( $1$ s).
3 2 1 0 2	5	Học sinh $A$ đi tới chồng $3$ và lấy $1$ hộp ở đó; học sinh $B$ đi qua chồng $1$ (lấy hộp), tiếp tục đến chồng $3$ và lấy $1$ hộp còn lại.
4 100 3 4 5 4	5	Có rất nhiều học sinh; chia mỗi chồng cho đủ số học sinh để dọn xong song song trong $5$ giây.

Bình luận

Không có bình luận tại thời điểm này.