Loki contre Heimdall – Regional event 2024

Level 3 ⋅ Validation weight: 40%

Énoncé

Loki et Heimdall s'affrontent, et viennent de lancer toutes leurs troupes dans la bataille. Les guerriers, vaillants mais voulant se ménager, tentent de choisir leurs adversaires en se déplaçant le moins possible.

La position des troupes de Loki et de Heimdall est renseignée dans les tableaux d'entiers loki et heimdall.

La distance entre une troupe en position $i$ et une troupe adverse en position $j$ est donnée par $(i - j)^2$. Les troupes vont systématiquement attaquer la troupe adverse la plus proche.

Aidez Jøsëf à calculer la distance totale que vont parcourir les troupes des deux dieux.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de troupes de Loki.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : loki, les positions des troupes de Loki.
  • Sur la ligne suivante, un entier : M, le nombre de troupes de Heimdall.
  • Sur la ligne suivante, une liste de M entiers séparés par des espaces : heimdall, les positions des troupes de Heimdall.

Sortie

Afficher, sur une ligne, la distance totale que vont parcourir les troupes.

Contraintes

  • $1 \le N \le 100$
  • $1 \le \text{loki[i]} \le 100$
  • $1 \le M \le 100$
  • $1 \le \text{heimdall[i]} \le 100$

Contraintes de performance

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

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
6 3 11
2
5 8
Sample output
19
Note

Loki possède trois troupes, en position $6$, $3$ et $11$. Heimdall possède deux troupes, en position $5$ et $8$.

Considérons les troupes de Loki.

  • La troupe en position $6$ va attaquer la troupe en position $5$, et va donc effectuer une distance de $1^2 = 1$
  • La troupe en position $3$ va attaquer la troupe en position $5$, et va donc parcourir une distance de $2^2 = 4$
  • La troupe en position $11$ va attaquer la troupe en position $8$, et va donc effectuer une distance de $3^2 = 9$

Considérons maintenant les troupes d'Hemdall.

  • La troupe en position $5$ va attaquer la troupe en position $6$, et va donc parcourir une distance de $1^2 = 1$
  • La troupe en position $8$ va attaquer la troupe en position $6$, et va donc effectuer une distance de $2^2 = 4$

La distance totale est donc de $1 + 4 + 9 + 1 + 4 = 19$.

Sample input
2
3 7
2
13 2
Sample output
63
Sample input
2
7 6
3
3 5 8
Sample output
13

Submit your solution

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