trang chủ / bài tập / bestvac

Kỳ Nghỉ Tuyệt Vời Nhất

Một năm ở nơi bạn sắp đến du lịch có $n$ tháng, tháng thứ $i$ có đúng $d_{i}$ ngày. Các ngày trong tháng thứ $i$ được đánh số từ $1$ đến $d_{i}$ .

Nếu bạn đi chơi vào ngày mang số thứ tự $j$ trong tháng (tức là ngày thứ $j$ của tháng đó), bạn nhận được $j$ điểm vui.

Kỳ nghỉ của bạn kéo dài đúng $x$ ngày liên tiếp. Kỳ nghỉ không nhất thiết phải bắt đầu và kết thúc trong cùng một năm: sau ngày cuối cùng của tháng $n$ , lịch quay lại ngày $1$ của tháng $1$ và cứ thế lặp lại (mọi năm giống hệt nhau, không có năm nhuận).

Hãy chọn ngày bắt đầu kỳ nghỉ sao cho tổng số điểm vui nhận được trong $x$ ngày liên tiếp là lớn nhất.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $x$ .
Dòng 2: $n$ số nguyên $d_{1}, d_{2}, \dots, d_{n}$ .

Dữ liệu ra

Một số nguyên duy nhất: tổng số điểm vui lớn nhất có thể nhận được.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq d_{i} \leq 10^{6}$
$1 \leq x \leq d_{1} + d_{2} + \dots + d_{n}$

Ví dụ

Input	Output	Giải thích
3 2 1 3 1	5	Dãy số thứ tự các ngày trong năm là 1, 1, 2, 3, 1. Bắt đầu từ ngày thứ ba của năm cho $2 + 3 = 5$ điểm.
3 6 3 3 3	12	Dãy số thứ tự là 1, 2, 3, 1, 2, 3, 1, 2, 3. Bắt đầu từ ngày thứ ba cho $3 + 1 + 2 + 3 + 1 + 2 = 12$ điểm.
5 6 4 2 3 1 3	15	Dãy là 1, 2, 3, 4, 1, 2, 1, 2, 3, 1, 1, 2, 3. Bắt đầu từ ngày thứ mười hai cho $2 + 3 + 1 + 2 + 3 + 4 = 15$ điểm.

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 6,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loạ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