Bạn có một dãy \(n\) số nguyên không âm và cần chia dãy thành \(k+1\) đoạn liên tiếp không rỗng. Ban đầu toàn bộ dãy là một đoạn. Lặp lại đúng \(k\) lần:

1. Chọn một đoạn có nhiều hơn một phần tử.
2. Cắt đoạn đó giữa hai phần tử liên tiếp để tạo thành hai đoạn không rỗng.

Mỗi lần cắt, bạn nhận số điểm bằng tích tổng các phần tử của hai đoạn mới tạo ra. Hãy tối đa hóa tổng điểm qua \(k\) lần cắt.

Dữ liệu vào

• Dòng đầu chứa \(n,k\), với \(k+1\le n\).
• Dòng thứ hai chứa \(n\) số \(a_1,a_2,\ldots,a_n\).

Dữ liệu ra

• Dòng đầu in tổng điểm lớn nhất.
• Dòng thứ hai in \(k\) số nguyên trong đoạn \([1,n-1]\), là các vị trí phần tử mà sau đó cần cắt dãy để đạt tổng điểm lớn nhất.

Nếu có nhiều phương án tối ưu, in bất kỳ phương án nào. Thứ tự các vị trí trên dòng thứ hai không ảnh hưởng đến kết quả cuối cùng, nhưng mỗi vị trí phải khác nhau và phải tạo ra đúng \(k+1\) đoạn không rỗng.

Ràng buộc

• \(0\le a_i\le10^4\).
• \(1\le k<n\le100\,000\).
• Trong các nhóm lớn, \(k\le200\).

Ví dụ

7 3
4 1 3 4 0 2 3

108
1 3 5

Giải thích

• Cắt sau phần tử \(1\), nhận \(4\times(1+3+4+0+2+3)=52\) điểm.
• Cắt đoạn thứ hai sau phần tử \(3\), nhận \((1+3)\times(4+0+2+3)=36\) điểm.
• Cắt đoạn cuối sau phần tử \(5\), nhận \((4+0)\times(2+3)=20\) điểm.

Tổng điểm là \(52+36+20=108\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Split the Sequence.