## APIO '14 P2 - Split the Sequence

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are playing a game with a sequence of non-negative integers. In this game you have to split the sequence into non-empty parts. To obtain parts you repeat the following steps times:

1. Choose any part with more than one element (initially you have only one part – the whole sequence).

2. Split it between any two elements to get two new non-empty parts.

Each time after these steps you gain the number of points which is equal to product of sums of elements of each new part. You want to maximize the total number of points you gain.

#### Input Specification

The first line of the input file contains two integers and (). The second line of input contains non-negative integers () – the sequence.

#### Output Specification

On the first line output the largest total number of points you can gain. On the second line output integers between and — the positions of elements after which you have to split the sequence to gain the largest total number of points. If there are more than one way to gain the largest number of points output any one of them.

#### Scoring

Your program will be tested on 6 sets of input instances as follows:

.

.

.

.

.

.

#### Sample Input

7 3
4 1 3 4 0 2 3

#### Sample Output

108
1 3 5

#### Note

In the first sample you can gain points by the following way:

• Initially you have the whole sequence as one part. You will split the sequence after 1st element and gain points.
• You have two parts . You will split the sequence after 3rd element and gain points.
• You have three parts . You will split the sequence after 5th element and gain points.

So, after the steps taken above you get four parts and gain points.