Joseph Marché – Épreuve régionale 2025

Niveau 7 ⋅ Validation weight: 5%

Énoncé

La troupe de Joseph a enfin pu désamorcer la machine ! Les malfaiteurs ont été arrêtés par Joseph Martial, qui veut remercier Joseph Marchand pour son aide.

En tant que dirigeant de la cité, Joseph Martial autorise Joseph à repartir avec deux objets de son choix, en quantité quasi illimitée. Cependant, Joseph aura bien du mal à faire démarrer son sous-marin s'il se montre trop cupide...

Joseph Martial propose $N$ types d'objets différents à emporter. Pour son voyage de retour, Joseph Marchand peut repartir avec au plus 2 types d'objets différents.

Chaque type d'objet est disponible en une certaine quantité, et chaque objet de ce type pèse un certain poids et possède une certaine valeur, propre au type de l'objet.

Votre objectif est de déterminer quels objets Joseph Marchand devrait embarquer dans son sous-marin afin de maximiser la somme des valeurs des objets transportés, sans dépasser la limite de poids imposée par son sous-marin.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'objets.
  • Sur la ligne suivante, un entier : limite, le poids maximal que peut transporter Joseph.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : poids, le poids de chaque objet.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : prix, le prix de chaque objet.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : quantite, la quantité disponible pour chaque objet.

Sortie

Afficher, sur une ligne, le prix maximal que peut obtenir Joseph Marchand en déplacant des instances de deux objets de son choix, en respectant les contraintes.

Contraintes

  • $2 \le N \le 10$
  • $0 \le \mathtt{limite} \le 1\,000$
  • $0 \le \mathtt{poids}_i \le 1\,000$
  • $0 \le \mathtt{prix}_i \le 1\,000$
  • $0 \le \mathtt{quantite}_i \le 1\,000$

Contraintes de performance

  • $2 \le N \le 1\,000$
  • $0 \le \mathtt{limite} \le 10^{18}$
  • $0 \le \mathtt{poids}_i \le 10^{9}$
  • $0 \le \mathtt{prix}_i \le 10^{9}$
  • $0 \le \mathtt{quantite}_i \le 10^{9}$

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
4
420
100 103 120 97
12 14 10 13
5 3 3 5
Exemple de sortie
55
Commentaire

Dans cet exemple, Joseph doit choisir deux objets parmi quatre objets différents :

  • A, disponible en 5 exemplaires, pèse 100kg et rapporte 12$
  • B, disponible en 3 exemplaires, pèse 103kg et rapporte 14$
  • C, disponible en 3 exemplaires, pèse 120kg et rapporte 10$
  • D, disponible en 5 exemplaires, pèse 97kg et rapporte 13$

Voyons simplement pour chaque paire d'objets $(i, j)$ sélectionnés le prix maximal que Joseph Marchand aurait pu transporter. On donne pour chaque paire $(i, j)$ un exemple de paire $(q_i, q_j)$ tel que prendre $q_i$ instances de l'élément $i$ et $q_j$ instances de l'élément $j$ remporte un prix maximal, sans dépasser la limite de poids.

$i$         $j$         $q_i$         $q_j$         gain         poids
A B 1 3 54$ 409kg
A C 4 0 48$ 400kg
A D 0 4 52$ 388kg
B C 3 0 42$ 309kg
B D 3 1 55$ 406kg
C D 0 4 52$ 388kg

En utilisant 3 instances de l'objet B et 1 instance de l'objet D, Joseph peut donc parvenir à obtenir un gain de $3 \times 14 + 1 \times 13 = 55$, pour un poids total de $3 \times 103 + 1 \times 97 = 406$, ce qui respecte la limite de poids de 420kg indiquée.