Tâches et échéances
Étant donné
n tâches, chacune assortie d'une échéance et du profit associé si elle est terminée avant cette échéance, vous souhaitez déterminer le profit total maximal que vous pouvez obtenir. Chaque tâche requiert 1 jour pour être achevée. Si vous ne terminez pas une tâche avant son échéance, vous ne touchez aucun profit.Vous commencez au jour 1. Quel est le profit maximal que vous pouvez obtenir ?
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ), qui représente le nombre de tâches.Les
n lignes suivantes contiennent des paires d’entiers séparées par un espace (1 ≤ , ≤ ), correspondant à l’échéance et au profit pour l’accomplissement de chaque tâche.Sortie
Le programme doit afficher le profit total maximal que vous pouvez obtenir.
Exemples
Input | Output |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Explications
- 10 + 3 + 7
- D’abord, exécuter la tâche dont l’échéance est 1 ⇒ profit 3
- Ensuite, exécuter la tâche dont l’échéance est 2 ⇒ profit 7
- Puis, exécuter la tâche dont l’échéance est 4 ⇒ profit 10
- 100 + 200 + 300 + 200 (n’exécuter que des tâches ayant une échéance de 4)
- Exécuter la tâche offrant un profit de 100
- Exécuter la tâche offrant un profit de 200
- Exécuter la tâche offrant un profit de 300
- Exécuter la tâche offrant un profit de 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB