Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Grammy tiene dos compañeros de equipo, A y B. Normalmente, los dos compañeros salen a comer a buenos restaurantes todos los días, mientras que Grammy suele comer en la cafetería de la escuela. Comer en la cafetería de la escuela ahorra tiempo y dinero, mientras que salir a comer a veces implica gastos de taxi. Aun así, hay ocasiones en las que Grammy decide salir con sus compañeros para mejorar sus comidas.

A medida que se acerca el final del mes, a Grammy solo le quedan $m$ yuanes para sus gastos de manutención, y necesita pasar los próximos $n$ días con este dinero. En el $i$-ésimo día, tiene dos opciones:

  • Comer en la cafetería, obteniendo una satisfacción de $a_i$ y gastando $b_i$ yuanes.
  • Salir a comer con sus compañeros de equipo, obteniendo una satisfacción de $c_i$ y gastando $d_i$ yuanes.

Como A y B salen a comer todos los días, habrá gastos de taxi cada día. Sea $e_i$ la tarifa del taxi en el $i$-ésimo día; los tres han establecido una regla para pagar el taxi:

  • Si Grammy no sale a comer en el $i$-ésimo día, entonces hay una probabilidad de $\frac{p_i}{100}$ de que A pague el taxi, y una probabilidad de $(1 - \frac{p_i}{100})$ de que pague B.
  • Si Grammy sale a comer en el $i$-ésimo día, y desde la última vez que Grammy pagó el taxi (o desde el primer día, si Grammy nunca ha pagado el taxi), tanto A como B han pagado el taxi al menos una vez cada uno (independientemente de si Grammy salió a comer en ese momento), entonces Grammy pagará el taxi esta vez. De lo contrario, uno de los compañeros pagará según la regla anterior.

Cada día, Grammy elegirá su acción antes de la comida. Ella sabrá quién pagó el taxi el día anterior, y su objetivo es maximizar la satisfacción total esperada, asegurándose de que los gastos totales no superen los $m$ yuanes en el peor de los casos. Si toma decisiones óptimas todos los días, ¿cuál es el valor esperado de la satisfacción total?

Entrada

Solo hay un caso de prueba en cada archivo de prueba.

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), que indican el número de días y el límite total de gastos.

En las siguientes $n$ líneas, la $i$-ésima línea contiene seis enteros $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ y $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$). Sus significados se describen arriba.

Salida

Imprime una línea con un único número, indicando el valor esperado máximo de la satisfacción total. Si no existe ningún plan en el que los gastos totales sean menores o iguales a $m$ yuanes en el peor de los casos, imprime $-1$.

Tu respuesta se considerará correcta si su error absoluto o relativo no supera $10^{-6}$. Formalmente, supongamos que tu salida es $a$ y la respuesta del jurado es $b$; tu salida será aceptada si y solo si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Ejemplos

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.