Le Retour de Joseph Macadam – Épreuve régionale 2025

Niveau 3 ⋅ Validation weight: 35%

Énoncé

Arrivé au point de rencontre indiqué par la lettre, il rencontre alors enfin son auteur. Quelle surprise ! Il s'agit du dirigeant de la ville lui-même, Joseph Martial !

Le dirigeant explique alors qu'il est lui aussi au courant des manigances qui se produisent dans la ville, et compte bien nous aider à les faire cesser. Notre objectif est maintenant de trouver la salle de contrôle où les dispositifs doivent sûrement se trouver.

Le dirigeant suspecte alors Joseph Macadam, l'agent d'exploitation des routes maritimes, d'être en fait affilié à ce complot. Après l'avoir interrogé, Joseph Macadam promet une nouvelle fois de réveler plus d'informations sur la tour de contrôle en échange d'une nouvelle aide pour son travail.

Une route est composée de $N$ portions. Chaque portion peut soit être trouée, soit être bouchée par des déblais. Les portions trouées sont indiquées dans la liste $\mathtt{route}$ par un nombre négatif, dont la valeur absolue représente le volume de manque à remplir. Les portions bouchées sont indiquées dans la liste $\mathtt{route}$ par un nombre positif, représentant la quantité de déblais qui bloque la portion.

Heureusement, le département des routes maritimes dispose de bulldozers afin de pousser les gravats de portion en portion suivante sur la route.

Cependant, cet engin ne peut pousser que $X$ unités de gravats simultanément. Il ne peut pas non plus franchir les trous présents sur les routes, mais ces derniers peuvent être comblés grâce aux gravats cumulés et poussés par le bulldozer.

Le bulldozer s'arrête d'avancer si le volume cumulé de gravats est supérieur à $X$, ou si un trou ne peut être comblé. L'engin avance de gauche à droite sur les portions.

Pour permettre à l'engin d'aller plus loin, Joseph peut à tout moment se vider de certains de ses gravats cumulés en les déposant sur le bas-côté de la route. Le volume maximum qu'il peut vider sur le bas-côté dépend de chaque tronçon $i$, et est indiqué en entrée par $\mathtt{bas cote}_i$.

En clair, pour chaque portion $i$ :

  • Si $\mathtt{route}_i$ est positif, alors l'engin accumule $\mathtt{route}_i$ unités de gravats supplémentaire.
  • Sinon, l'engin doit, si possible, déposer $-\mathtt{route}_i$ gravats précédemment cumulés pour combler le trou dans la portion.
  • Dans tous les cas, l'engin peut se vider d'au plus $\mathtt{bas cote}_i$ gravats cumulés sur le bas-côté. Cette action n'est pas limitée par la capacité $X$ de la machine.
  • Si l'engin a réussi à entièrement combler l'éventuel trou, et que sa quantité de déblais ne dépasse pas $X$, alors cette portion est considérée comme nettoyée, et l'engin peut avancer à la portion suivante.

Aidez Joseph à déterminer le nombre maximal de portions de routes que sa machine peut déblayer.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de portions de la route.
  • Sur la ligne suivante, un entier : X, la puissance de l'engin.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : route, le volume de déblais sur chaque portion de la route.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : bas cote, la quantité maximale de déblais pouvant être déplacés pour chaque portion.

Sortie

Afficher, sur une ligne, le nombre maximal de portions que la machine pourra traverser.

Contraintes

  • $1 \le N \le 10$
  • $0 \le X \le 1\,000\,000\,000$
  • $-1\,000\,000\,000 \le \mathtt{route}_i \le 1\,000\,000\,000$
  • $0 \le \mathtt{bas cote}_i \le 1\,000\,000\,000$

Contraintes de performance

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

Joseph dispose ici d'un bulldozer ayant une capacité de $5$.

  • Parmi les $3$ gravats présents sur le premier tronçon, Joseph choisit d'en délaisser $1$ sur le bas-côté, et d'en pousser $2$ sur le tronçon suivant.
  • Il se retrouve donc avec $5$ gravats à pousser, qu'il pousse entièrement sur le troisième tronçon.
  • Parmi les $5$ gravats qui arrivent sur le troisième tronçon, $3$ d'entre eux servent à remplir le trou présent sur la chaussée. Les $2$ autres sont poussés sur le tronçon suivant.
  • On se retrouve alors avec $3$ gravats, qui sont tous poussés sur le dernier tronçon.
  • Les $3$ gravats arrivant au dernier tronçon suffisent à combler le dernier trou présent sur la chaussée. Le bulldozer parvient alors à nettoyer l'intégralité de la route !

Comme les $5$ portions de routes ont pu être nettoyées, la réponse attendue est $5$.

schema

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

Joseph dispose ici d'un bulldozer ayant une capacité de $3$.

  • Parmi les $5$ gravats présents sur le premier tronçon, Joseph choisit d'en délaisser $2$ sur le bas-côté, et de pousser les $3$ restants sur le tronçon suivant.
  • Il se retrouve donc avec $5$ gravats à pousser depuis le deuxième tronçon, dont il en délaisse une nouvelle fois $2$ sur le bas-côté afin de pousser les $3$ restants.
  • Parmi les $3$ gravats qui arrivent sur le troisième tronçon, $1$ d'entre eux sert à remplir le trou présent sur la chaussée. Joseph choisit d'en délaisser $1$ supplémentaire sur le bas-côté, et de pousser le gravat restant sur le tronçon suivant.
  • On se retrouve alors avec $6$ gravats sur le dernier tronçon. Malheureusement, même en délaissant $2$ gravats sur le bas-côté, il resterait $4$ gravats à pousser, ce qui est supérieur à la puissance du bulldozer de Joseph.

Ainsi, Joseph parvient à nettoyer $3$ des $4$ portions de routes. Il n'est pas possible de nettoyer les $4$ portions de route, alors la solution attendue est $3$.

schema