Distraquetion – Épreuve régionale 2025

Niveau 5 ⋅ Validation weight: 10%

Énoncé

Arrivés devant la présupposée tour de contrôle, Joseph Marchand et Joseph Martial y trouvent deux gardes devant les différentes entrées de la tour. Il s'agit de Traque & Matraque ! Ils vont devoir effectuer une distraction pour réussir à rentrer sans se faire remarquer.

Joseph dispose de $K$ cailloux pour effectuer sa distraction. La tour possède $N$ portes d'entrées, et initialement Traque se situe devant la première porte d'entrée, notée porte $1$, tout à gauche, et Matraque se situe devant la dernière porte d'entrée, notée porte $N$, tout à droite. Les gardes couvrent ainsi toutes les portes situées entre eux.

Joseph doit alors effectuer une distraction en lançant au moins $1$ caillou, et jusqu'à $K$ cailloux devant des portes distinctes. Après avoir lancé les cailloux, Traque va se diriger vers le caillou $G$ le plus à gauche, et Matraque vers le caillou $D$ le plus à droite. Ainsi, Traque et Matraque ne couvriront plus que $D - G$ portes.

Chaque porte possède un $\mathtt{score}$ d'intérêt, qui indique à quel point jeter un caillou devant cette porte serait efficace. (Attention, $\mathtt{score}$ peut être négatif !)

L'objectif de Joseph est à la fois de faire une distraction ayant un gros score d'intérêt (sinon les gardes ne vont pas y prêter attention), et de faire en sorte que les gardes se rapprochent le plus possible afin de s'offrir le plus d'occasion de rentrer dans la tour sans se faire remarquer. Plus formellement, l'efficacité de la distraction sera égale à la somme des $\mathtt{score}$ d'intérêt des portes ciblées, moins la distance $D - G$.

Aidez Joseph à déterminer comment effectuer une distraction optimale.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de portes.
  • Sur la ligne suivante, un entier : K, le nombre maximal de cailloux que Joseph peut lancer.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : score, le score d'intérêt de chaque porte.

Sortie

Afficher, sur une première ligne, l'efficacité maximale que Joseph peut atteindre pour sa distraction. Sur une seconde ligne, afficher le nombre de cailloux que Joseph Marchand va lancer. Finalement, sur une troisième ligne, séparés par des espaces, afficher les indices des portes sur lesquelles Joseph Marchand va lancer un caillou. Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Contraintes

  • $1 \le N \le 10$
  • $1 \le K \le N$
  • $-10\,000 \le \mathtt{score}_i \le 10\,000$

Contraintes de performance

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

Contraintes d'exécution

Utilisation mémoire maximum
400000 kilo-octets
Temps d'exécution maximum
3000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
2
9 1 7 2 8
Exemple de sortie
14
2
1 3
Commentaire

En lançant deux cailloux devant les portes $1$ et $3$, de score respectivement $9$ et $7$, les gardes se rapprochent à une distance de $3 - 1 = 2$ mètres. La distraction atteint alors une efficacité de $9 + 7 - 2 = 14$. Il n'est pas possible d'obtenir une meilleure efficacité.

Exemple d'entrée
8
4
4 3 -1 1 0 7 9 8
Exemple de sortie
22
3
6 7 8
Commentaire

Ici, il est préférable pour Joseph Marchand de ne lancer que $3$ cailloux, même s'il était autorisé d'en lancer $4$.

En lançant les cailloux devant les portes $6$, $7$ et $8$, de score respectivement $7$, $9$ et $8$, Joseph s'en sort avec une efficacité de $7 + 9 + 8 - (8 - 6) = 22$. Il n'est pas possible d'obtenir plus grande efficacité.

Exemple d'entrée
4
2
4 1 2 3
Exemple de sortie
4
2
1 2
Commentaire

Ici, il existe plusieurs possibilités pour Joseph Marchand :

  • Lancer un caillou uniquement devant la première porte, pour une efficacité de $4 - 0 = 4$
  • Lancer un caillou devant la première et troisième porte, pour une efficacité de $4 + 2 - 2 = 4$
  • Lancer un caillou devant la première et la dernière porte, pour une efficacité de $4 + 3 - 3 = 4$
  • Lancer un caillou devant les deux dernières portes, pour une efficacité de $2 + 3 - 1 = 4$.

Toutes ces réponses sont considérées comme valides. Il n'est pas possible d'obtenir une efficacité supérieure à $4$.