Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Grammy ha due compagni di squadra, A e B. Di solito i due compagni vanno a mangiare fuori in ottimi ristoranti ogni giorno, mentre Grammy mangia generalmente alla mensa scolastica. Mangiare alla mensa scolastica fa risparmiare tempo e denaro, mentre andare fuori a volte comporta spese per il taxi. Nonostante ciò, ci sono volte in cui Grammy sceglie di uscire con i suoi compagni di squadra per migliorare i propri pasti.

Con l'avvicinarsi della fine del mese, a Grammy restano solo $m$ yuan per le spese di sostentamento, e deve affrontare i successivi $n$ giorni con questi soldi. Nel giorno $i$-esimo ha due scelte:

  • Mangiare in mensa, ottenendo una soddisfazione pari ad $a_i$ e spendendo $b_i$ yuan.
  • Uscire a mangiare con i suoi compagni di squadra, ottenendo una soddisfazione pari a $c_i$ e spendendo $d_i$ yuan.

Poiché A e B escono a mangiare ogni giorno, ci saranno spese di taxi ogni giorno. Sia $e_i$ la tariffa del taxi nel giorno $i$-esimo; i tre hanno stabilito una regola per pagare il taxi:

  • Se Grammy non esce a mangiare nel giorno $i$-esimo, allora c'è una probabilità $\frac{p_i}{100}$ che A paghi il taxi e una probabilità $(1 - \frac{p_i}{100})$ che paghi B.
  • Se Grammy esce a mangiare nel giorno $i$-esimo e, dall'ultima volta in cui Grammy ha pagato il taxi (o dal primo giorno, se Grammy non ha mai pagato il taxi), sia A che B hanno pagato il taxi almeno una volta ciascuno (indipendentemente dal fatto che Grammy fosse uscita a mangiare in quell'occasione), allora questa volta sarà Grammy a pagare il taxi. Altrimenti, uno dei compagni pagherà secondo la regola precedente.

Ogni giorno, Grammy sceglierà la sua azione prima del pasto. Saprà chi ha pagato il taxi il giorno precedente, e il suo obiettivo è massimizzare il valore atteso della soddisfazione totale, garantendo al contempo che le spese totali non superino $m$ yuan nel caso peggiore. Se prende decisioni ottimali ogni giorno, qual è il valore atteso della soddisfazione totale?

Dati di ingresso

C'è un solo caso di test in ciascun file di test.

La prima riga contiene due interi $n$ e $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), che indicano il numero di giorni e il limite massimo di spesa totale.

Per le successive $n$ righe, la $i$-esima riga contiene sei interi $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ e $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$). I loro significati sono descritti sopra.

Dati di uscita

Stampa una riga contenente un singolo numero, che indica il massimo valore atteso della soddisfazione totale. Se non esiste alcun piano in cui le spese totali siano minori o uguali a $m$ yuan nel caso peggiore, stampa $-1$.

La tua risposta sarà considerata corretta se il suo errore assoluto o relativo non supera $10^{-6}$. Formalmente, supponendo che il tuo output sia $a$ e la risposta della giuria sia $b$, il tuo output è accettato se e solo se $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esempi

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.