Tóm tắt đề bài: Chọn ra một vài trạm phát sóng sao cho:

• Khoảng cách giữa hai trạm phát sóng bất kỳ ~\ge k~.
• Tổng lợi nhuận của các trạm phát sóng đó là lớn nhất.

Subtask 1: ~n \le 1000~

Gọi ~dp_i~ là lợi nhuận lớn nhất khi xét đến trạm phát sóng thứ ~i~, bắt buộc chọn trạm phát sóng thứ ~i~.

Ta thấy, ~dp_i = max (a_i, dp_j + a_i)~ với điều kiện ~1 \le j \le i - 1~ và ~p_i - p_j \ge k~.

Độ phức tạp: ~O~ (~n^2~).

Subtask 2, 3: ~n \le 10^6~

Ta có thể duy trì ~x~, là vị trí lớn nhất thỏa mãn ~p_i - p_x \ge k~ bằng hai con trỏ.

Lúc này, ta có công thức truy hồi mới: ~dp_i = max (a_i, max (dp_1, dp_2, ..., dp_x) + a_i)~.

Để xử lý nhanh phần này, ta gọi ~f_i = max (dp_1, dp_2, ..., dp_i)~.

Lúc này, công thức truy hồi là: ~dp_i = max (a_i, f_x + a_i)~.

Độ phức tạp: ~O~ (~n~).

Lưu ý: Dữ liệu vào rất lớn, mình đã chỉnh giới hạn thời gian ở 5 giây. Nếu muốn cải tiến hơn nữa, có thể sử dụng fast input, sẽ AC trong 1 giây.