Couplage – Épreuve régionale 2014

Enoncé¶

Laszlo Carreidas, milliardaire peu respectable, n'est pas très bon perdant. Après avoir perdu pour la dix-septième fois de suite une partie de Couplage, il en a, si vous lui permettez l'expression, ras-le-bol.

Laszlo a donc décidé d'engager ses meilleurs algorithmiciens pour concevoir et programmer un algorithme capable de trouver à tous les coups la meilleure solution à ce jeu pour ne plus jamais perdre, et ainsi honorer sa réputation.

Le principe du jeu de couplage est très simple :

On donne à chaque joueur un boulier comportant deux barres en métal (on les considérera infiniment grandes), le long desquelles peuvent librement se mouvoir des boules numérotées.

Lorsqu'on met deux boules de valeur égales l'une en face de l'autre, on gagne la valeur indiquée sur ces boules, qui est ajoutée à son score.

Le but du jeu est d'aligner les boules de manière à avoir le plus de boules de valeur égales l'une en face de l'autre.

On vous demande de trouver le score maximum qu'il est possible de faire en agençant ces boules de manière optimale.

Entrée¶

• Sur la première ligne, le nombre la de boules de la première barre
• Sur la deuxième ligne, le nombre lb de boules de la deuxième barre
• Sur la troisième ligne, les valeurs a_i des boules de la première barre
• Sur la quatrième ligne, les valeurs b_i des boules de la deuxième barre

Sortie¶

Le score maximum qu'il est possible d'atteindre en alignant les boules sur les barres.

Contraintes¶

• 1 <= la <= 2 000
• 1 <= lb <= 2 000
• 0 <= a_i <= 1 000
• 0 <= b_i <= 1 000