Canadian Computing Olympiad: 2019 Day 2, Problem 1

You have a deck of ~n~ cards. Each card has a value: the card values lie between ~1~ to ~n~, possibly with some repeated values, and possibly with some values never occurring. There is also a special integer ~k~ that will be used in calculating a score.

You are playing a game that involves drawing all the cards from the deck one by one. When you draw a card, you may choose to either add it to your hand or discard it. You may also score your entire hand at any time. When you score a hand with ~x~ cards, you gain ~x^{k/2}~ points and then you discard all cards in that hand. At any point in time, your hand may only contain cards with the same number on them. Given the initial order of the cards in the deck, what is the maximum possible score you can obtain?

Input Specification

The first line of input will contain two space-separated integers ~k~ and ~n~. The value ~k~ is the value used in the expression ~x^{k/2}~ to compute points ~(2 \le k \le 4)~. The value ~n~ is the number of cards in the deck ~(1 \le n \le 1\,000\,000)~. The next ~n~ lines contain one integer per line, where the ~i^{th}~ of these ~n~ lines is the ~i^{th}~ card from the top of the deck ~(1 \le i \le n)~.

For 4 of the 25 marks available, ~1 \le n \le 20~.

For an additional 1 of the 25 marks available, ~1 \le n \le 300~, ~k = 2~.

For an additional 5 of the 25 marks available, ~1 \le n \le 300~.

For an additional 3 of the 25 marks available, ~1 \le n \le 5\,000~.

For an additional 3 of the 25 marks available, ~k = 4~.

Output Specification

Output one floating point number, which is the maximum score you can obtain from playing optimally.

If your answer is ~p~ and the correct answer is ~q~, then your answer will be considered correct if

$$\displaystyle \frac{|p-q|}{q} \le 10^{-6}$$

Sample Input 1

3 5
1
2
2
1
1

Output for Sample Input 1

6.656854249

Explanation for Output for Sample Input 1

We know the cards we draw in order are ~[1, 2, 2, 1, 1]~ and that discarding a hand of ~x~ cards gives us a score of ~x^{1.5}~.

The optimal strategy is to draw one card, score that hand, draw two cards, score that hand, and draw two more cards and score that hand. This strategy gives a score of ~1^{1.5}+2^{1.5}+2^{1.5} \approx 6.656854249~.

Sample Input 2

4 5
1
2
2
1
1

Output for Sample Input 2

9.0

Explanation of Output for Sample Input 2

We know the cards we draw in order are ~[1, 2, 2, 1, 1]~ and that scoring a hand of ~x~ cards gives us a score of ~x^2~.

An optimal strategy is to take all cards with ~1~, and score them all at the end. This strategy gives a score of ~3^2 = 9~. Note that taking the first card and scoring, then taking the next two cards and scoring, and then taking the final two cards and scoring, will also yield ~1^2 + 2^2 + 2^2 = 9~.