🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sáng sớm ở chợ nổi Cái Răng, ~N~ chiếc ghe hàng đậu thành một hàng dài dọc bờ sông, đánh số từ ~1~ đến ~N~ theo thứ tự. Trên mỗi ghe có một cây bẹo – cây sào dựng đứng treo mẫu hàng ghe đó bán để khách nhìn từ xa là biết. Cây bẹo của ghe thứ ~i~ cao ~h_i~.

Thầy Sơn mang máy ảnh ra chợ để làm tư liệu cho học trò. Mỗi tấm ảnh thầy chụp đúng một dãy ghe liên tiếp từ ghe ~l~ đến ghe ~r~ ~(1 \le l \le r \le N)~. Mỗi ghe chiếm đúng ~1~ đơn vị bề ngang. Khung ảnh phải đủ rộng để lấy hết các ghe và đủ cao để lấy trọn cây bẹo cao nhất. Do đó khung ảnh của dãy ~[l, r]~ có diện tích

~S(l, r)~ ~= (r - l + 1) \times \max(h_l, h_{l+1}, \ldots, h_r).~

Có tất cả ~\frac{N(N+1)}{2}~ cách chọn dãy ghe. Thầy Sơn tính diện tích khung ảnh của mọi dãy rồi xếp các diện tích theo thứ tự không giảm. Hai dãy khác nhau có cùng diện tích vẫn được tính là hai tấm. Tiệm in ảnh trên bờ chỉ còn đủ giấy để in tấm thứ ~K~ trong danh sách đó. Hãy giúp thầy Sơn biết tấm ảnh thứ ~K~ có diện tích bằng bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, K~ ~(1 \le N \le 3 \times 10^5,~ ~1 \le K \le \frac{N(N+1)}{2})~.
• Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2, \ldots, h_N~ ~(1 \le h_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là diện tích thứ ~K~ (theo thứ tự không giảm) trong các diện tích khung ảnh.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~K \le 10^6~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 4 giây.

Sample Input 1

4 6
3 1 4 2

Sample Output 1

8

Giải thích

Có ~10~ dãy ghe:

• Dãy 1 ghe: ~[1,1], [2,2], [3,3], [4,4]~ có diện tích ~3, 1, 4, 2~.
• Dãy 2 ghe: ~[1,2]~ có diện tích ~2 \times 3 = 6~; ~[2,3]~ và ~[3,4]~ đều có ~2 \times 4 = 8~.
• Dãy 3 ghe: ~[1,3]~ và ~[2,4]~ đều có ~3 \times 4 = 12~.
• Dãy 4 ghe: ~[1,4]~ có ~4 \times 4 = 16~.

Xếp không giảm: ~1, 2, 3, 4, 6, 8, 8, 12, 12, 16~. Tấm thứ ~6~ có diện tích ~8~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).