Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Grammy a deux coéquipiers A et B. D'habitude, ses deux coéquipiers sortent manger dans de bons restaurants tous les jours, tandis que Grammy mange généralement à la cafétéria de l'école. Manger à la cafétéria de l'école permet d'économiser du temps et de l'argent, alors que sortir entraîne parfois des frais de taxi. Malgré cela, il arrive que Grammy choisisse de sortir avec ses coéquipiers pour améliorer ses repas.

À l'approche de la fin du mois, il ne reste plus à Grammy que $m$ yuans pour ses dépenses courantes, et elle doit tenir les $n$ prochains jours avec cet argent. Le $i$-ème jour, elle a deux choix :

  • Manger à la cafétéria, ce qui lui procure une satisfaction de $a_i$ et lui coûte $b_i$ yuans.
  • Sortir manger avec ses coéquipiers, ce qui lui procure une satisfaction de $c_i$ et lui coûte $d_i$ yuans.

Comme A et B sortent manger tous les jours, il y a des frais de taxi chaque jour. Soit $e_i$ le prix du taxi le $i$-ème jour ; tous les trois ont établi une règle pour payer la course de taxi :

  • Si Grammy ne sort pas manger le $i$-ème jour, alors il y a une probabilité $\frac{p_i}{100}$ que A paie le taxi, et une probabilité $(1 - \frac{p_i}{100})$ que B paie.
  • Si Grammy sort manger le $i$-ème jour, et que depuis la dernière fois où Grammy a payé le taxi (ou depuis le premier jour si Grammy n'a jamais payé le taxi), A et B ont chacun payé le taxi au moins une fois (que Grammy soit sortie manger ou non à ce moment-là), alors c'est Grammy qui paie le taxi cette fois-ci. Sinon, l'un des coéquipiers paiera selon la règle précédente.

Chaque jour, Grammy choisit son action avant le repas. Elle sait qui a payé le taxi la veille, et son objectif est de maximiser l'espérance de la satisfaction totale, tout en s'assurant que le total des dépenses ne dépasse pas $m$ yuans dans le pire des cas. Si elle prend des décisions optimales chaque jour, quelle est l'espérance de la satisfaction totale ?

Entrée

Il n'y a qu'un seul cas de test dans chaque fichier de test.

La première ligne contient deux entiers $n$ et $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), indiquant le nombre de jours et la limite totale de dépenses.

Pour les $n$ lignes suivantes, la $i$-ème ligne contient six entiers $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ et $p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$). Leurs significations sont décrites ci-dessus.

Sortie

Affichez une ligne contenant un seul nombre, indiquant l'espérance maximale de la satisfaction totale. S'il n'existe aucun plan permettant de garantir que les dépenses totales seront inférieures ou égales à $m$ yuans dans le pire des cas, affichez $-1$.

Votre réponse sera considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-6}$. Formellement, en supposant que votre sortie soit $a$ et que la réponse du jury soit $b$, votre sortie est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exemples

2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.