\(6^{th}\) round, February \(7^{th}\) 2015
Assume you are given an array A of \(N\) integers, array ID of \(N +1\) integers from the interval [1, \(N - 1\)]
and an integer \(R\).
We are doing a Warsha\(ll-Tu\)ri\(ng-Fo\)urier transformation^{1} on array A in the following way:
s\(um = 0\)
for \(i = 1\) to N
ind\(ex = mi\)n{ ID[i], ID[\(i+1\)] }
s\(um = su@@RISE_MATH_BLOCK_0@@m + A\)[index]
rotate array A to the right by R places
You are given the array A and constant \(R\), but you are not familiar with the array ID. What is the
largest possible value of variable sum after execution of the above algorithm?

In test cases worth 20% of total points, it will hold \(N\) ⩽7.
In test cases worth 60% of total points, it will hold \(N\) ⩽300.

The first line of input contains the integers \(N\) and \(R\) (2 ⩽\(N\) ⩽3 000, 1 ⩽\(R < N\)) from the task.
The second line of input contains the elements of array A, respectively from A[1] to A[\(N\)]. These are
integers from the interval [−\(10^{4}\), \(10^{4}\)].

The first line of output must contain the maximal value of sum.
The second line of output must contain the array ID of \(N + 1\) integers from the interval [1, \(N - 1\)] for
which the algorithm outputs the maximal sum. If there are multiple such arrays, output any.
If only the first line is correct (regardless of whether the second is printed), you will get 50% of points
for the corresponding test case.

생성자가 기록되지 않았습니다.

출처 COCI 2014/2015 Contest 6