Stabilisateurs – Qualification 2023

Niveau 4

Énoncé

Impossible de se connecter à Netflux et tous les cinémas sont fermés... Mais finalement, rien ne remplace l'expérience de l'univers du film. Vivre aux époques passées ou futures de ces productions donne envie à nos jeunes ingénieurs en herbe. Ils décident donc, tout naturellement, de construire une machine à voyager à travers les univers.

Oscar se charge de s'assurer de la stabilité inter-temporelle de la machine. Qui sait dans quel univers nos amis pourraient atterrir si la machine partait en biberine !

Afin de stabiliser la machine, il dispose de $K$ stabilisateurs spatio-temporels, ainsi que de $N$ accroches. Pour mettre en place un stabilisateur, il faut l'attacher à précisément 4 accroches. De plus, une accroche ne peut servir que pour un seul stabilisateur.

Si les 4 accroches sont toutes situées exactement à la même hauteur, le stabilisateur possède un indice de stabilité égal à $P$. Cependant, si les 4 accroches ne sont pas toutes situées exactement à la même hauteur, cela peut entraîner un déséquilibre.

On appelle le "déséquilibre" d'un stabilisateur la différence entre la plus haute et la plus basse de ses accroches, au carré. Par exemple, si un stabilisateur repose sur 4 accroches de hauteur 6, 5, 6, et 7, le stabilisateur possède un déséquilibre de $(7 - 5)^2 = 4$.

Si un stabilisateur possède un déséquilibre, alors son indice de stabilité vaut $P$ moins son déséquilibre.

L'indice de stabilité de la machine après avoir positionné un certain nombre de stabilisateurs est la somme des indices de stabilité de tous les stabilisateurs positionnés.

Vous n'êtes pas obligés de positionner tous les stabilisateurs.

Aidez Oscar à trouver l'indice de stabilité maximal qu'il peut obtenir pour la machine !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, nombre d'accroches.
  • Sur la ligne suivante, un entier : K, nombre de stabilisateurs.
  • Sur la ligne suivante, un entier : P, indice de stabilité parfaite.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : accroches_1, ..., accroches_N, hauteur de chaque accroche.

Sortie

Afficher l'indice de stabilité maximal obtenable.

Contraintes

  • $1 \le N \le 12$
  • $1 \le K \le N$
  • $1 \le P \le 100\,000$
  • $1 \le accroches_i \le 1\,000\,000\,000$

Contraintes de performance

  • $1 \le N \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
9
2
10
3 1 4 5 5 9 2 5 7
Exemple de sortie
9
Commentaire

Exemple

Ici, positionner un stabilisateur avec les accroches de hauteur 4, 5, 5, et 5 permet d'obtenir un indice de stabilité de $10 - (5 - 4)^2 = 9$. Même en positionnant deux stabilisateurs, il n'est ici pas possible d'obtenir une meilleur stabilité.

Exemple d'entrée
10
3
100
3 1 4 4 5 9 2 6 7 4
Exemple de sortie
187
Commentaire

Exemple

Ici, positionner deux stabilisateurs s'avère être plus optimal.

En effet, positionner un stabilisateur sur les accroches de hauteur 1, 2, 3, et 4 ajoute à l'indice de stabilité $100 - (4 - 1)^2 = 91$, et positionner un stabilisateur sur les accroches de hauteur 4, 4, 5 et 6 augmente de $100 - (6 - 4)^2 = 96$ l'indice de stabilité.

L'indice de stabilité total de la machine est donc de $91 + 96 = 187$

Exemple d'entrée
8
1
25
3 2 4 4 5 4 2 6
Exemple de sortie
24
Commentaire

Exemple

Ici, vous ne disposez malheureusement que d'un seul stabilisateur. Deux solutions optimales existent: (3, 4, 4, 4) et (4, 4, 4, 5). Dans les deux cas, l'indice de stabilité total est de $25 - 1^2 = 24$.