Couplage – Regional event 2014

Level 6

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 ai des boules de la première barre
  • Sur la quatrième ligne, les valeurs bi 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 <= ai <= 1 000
  • 0 <= bi <= 1 000

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
3
2 3 2
2 2 3
Sample output
5
Note

La meilleure solution ici est d'aligner un 2 et un 3 :

1
2
--2---3-2--
--2-2-3----

Notre score est donc 2 + 3 = 5.

Sample input
5
5
4 9 5 2 1
4 5 9 1 10
Sample output
14
Note

Ici, il est préférable d'aligner le 9, qui rapporte plus de points que d'aligner le 5.

1
2
--4---9-5-2-1-----
--4-5-9-----1-10--

Notre score maximum est donc 4 + 9 + 1 = 14.

Sample input
10
10
1 2 3 4 5 5 4 3 2 1
5 4 3 2 1 1 2 3 4 5
Sample output
15

Submit your solution

You have to register or log in to be able to submit your solution.