Divertissement Dilemmatique – Épreuve régionale 2023

Niveau 8

Énoncé

Cyril s'exclame de joie ! Grâce à votre aide, il a réussi à obtenir le courant parfait avec une précision remarquable. Valérian invite une nouvelle fois nos aventuriers à monter dans la machine, destination le futur ! Encodage du déplacement, activations des leviers, vérification du circuit de refroidissement, positionnement des stabilisateurs sur les bonnes accroches, appui sur le gros bouton rouge, et nos amis sont partis pour un nouveau voyage.

La machine s'arrête alors. Julie, toute excitée, ouvre la porte et se jette en dehors de la machine, et y découvre une ville comme personne n'en avait jamais vu auparavant. Ils ont réussi ! Cependant, quand il s'agit de se décider sur une activité, nos amis sont réputés pour ne pas se mettre d'accord si facilement. Rappelons-nous tout de même que toute cette histoire n'aurait peut-être pas eu lieu s'ils s'étaient directement mis d'accord sur le film à regarder…

Le groupe de nos six amis semble maintenant divisé. Julie, Oscar et Augustin veulent absolument aller essayer un parc d'attractions du futur qu'ils ont aperçu, tandis que Valérian, Raphaël et Cyril veulent visiter un centre de recherche scientifique, pour découvrir toutes les avancées technologiques à venir. C'est pourquoi l'objectif de cet exercice va être de résoudre l'un des plus grands problèmes que rencontrent tous les humains : faire des choix.

Nos amis ont décidé de visiter la ville pendant N jours. Chaque jour, le groupe peut soit aller visiter le parc d'attractions, soit visiter le centre de recherche, soit se reposer. Le jour i, si le groupe décide d'aller visiter le parc d'attractions, le bonheur du groupe augmente de $X_i$ ; si le groupe décide d'aller visiter le centre de recherche, le bonheur du groupe augmente de $-X_i$ ; et si le groupe décide de se reposer, le bonheur du groupe n'est pas altéré. (Notez que $X_i$ peut être négatif !)

Cependant, pour ne pas favoriser une certaine partie du groupe et pour éviter trop de redondance, pour n'importe quelle période de L jours consécutifs totalement incluse dans les N jours d'exploration, si le groupe va visiter $p$ fois le parc d'attractions et $r$ fois le centre de recherches, alors $|p - r|$ ne doit surtout pas dépasser K (où L et K sont deux entiers donnés en entrée.)

Aidez nos amis à planifier leur séjour dans le futur, et indiquez le bonheur maximal que le groupe peut obtenir.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, la durée prévue, en jours, de leur séjour dans le futur.
  • Sur la ligne suivante, un entier : L, le nombre de jours consécutifs durant laquelle les deux activités ne doivent pas être trop déséquilibrées.
  • Sur la ligne suivante, un entier : K, la différence maximale entre les occurences des deux activités tolérées pendant une période de L jours consécutifs.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : X, la liste des valeurs de bonheur apporté selon les activités.

Sortie

Afficher le bonheur maximal que le groupe peut atteindre

Contraintes

  • $1 \le N \le 100$
  • $1 \le L \le N$
  • $0 \le K \le L$
  • $-10\,000 \le X_i \le 10\,000$

Contraintes de performance

  • $1 \le N \le 3\,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
3
2
1
1 1 1
Exemple de sortie
2
Commentaire

Il a été décidé que leur séjour durerait précisément trois jours. Chaque jour, si le groupe décide d'aller visiter le parc d'attractions, alors le bonheur du groupe augmente de 1. Si le groupe décide d'aller visiter le centre de recherches, le bonheur du groupe diminue de 1. Si le groupe se repose, le bonheur du groupe ne change pas.

Pour éviter la redondance, pour tous deux jours consécutifs, la différence entre le nombre de fois où le groupe visite un parc d'attractions et le nombre de fois où le groupe visite le centre de recherche ne doit pas dépasser 1. C'est à dire qu'il est impossible de visiter deux fois le parc d'attractions deux jours d'affilée, ni de visiter deux fois le centre de recherches deux jours d'affilée.

La solution optimale consiste à aller visiter le parc d'attractions le premier jour, se reposer le deuxième jour, et aller visiter une nouvelle fois le parc d'attractions le troisième jour, pour un bonheur total de 2.

Exemple d'entrée
6
3
1
0 -2 1 -1 -4 -5
Exemple de sortie
11
Commentaire

Ici, pendant leur séjour d'une durée totale de 6 jours, nos jeunes ont décidés que, pour toute période de trois jours consécutifs, la différence entre le nombre de visite du parc d'attractions et le nombre de visite du centre de recherche ne devait pas excéder 1. C'est à dire que, pour toute période de trois jours consécutifs, nos jeunes ont le choix entre :

  • Se reposer les trois jours
  • Visiter le centre un jour, se reposer les deux autres jours
  • Visiter le parc un jour, se reposer les deux autres jours
  • Visiter le parc un jour, le centre un autre jour, se reposer le troisième jour
  • Visiter le centre deux jours, visiter le parc l'autre jour
  • Visiter le parc deux jours, visiter le centre l'autre jour.

Il est en revanche interdit que, durant n'importe quelle période de trois jours consécutifs :

  • ils visitent le parc les trois jours
  • ils visitent le centre les trois jours
  • ils visitent le parc deux jours et se repose l'autre jour
  • ils visitent le centre deux jours et se repose l'autre jour

Dans notre cas, une solution optimale serait de :

  • se reposer le premier jour, ce qui ne rapporte pas de bonheur au groupe
  • aller voir le centre de recherches le deuxième jour, ce qui rapporte deux points de bonheur au groupe
  • aller voir le parc d'attractions le troisième jour, ce qui rapporte un point de bonheur au groupe
  • aller voir le parc d'attractions le quatrième jour, ce qui fait perdre un point de bonheur au groupe
  • aller visiter le centre de recherches le cinquième jour, ce qui fait gagner quatre points de bonheur au groupe
  • aller visiter le centre de recherches le dernier jour, ce qui fait gagner cinq points de bonheur au groupe.

Le bonheur total ainsi obtenu est de 11. Il est impossible d'en obtenir plus en respectants les conditions indiquées.