Universal Cup Judging System

Universal Cup

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

Grammy hat zwei Teamkollegen A und B. Normalerweise gehen die beiden Teamkollegen jeden Tag in guten Restaurants essen, während Grammy meistens in der Schulmensa isst. In der Schulmensa zu essen spart Zeit und Geld, wohingegen das Auswärtsessen manchmal Taxikosten verursacht. Trotzdem gibt es Tage, an denen Grammy sich entscheidet, mit ihren Teamkollegen essen zu gehen, um sich eine bessere Mahlzeit zu gönnen.

Als das Monatsende näher rückt, hat Grammy nur noch $m$ Yuan für ihren Lebensunterhalt übrig, und sie muss mit diesem Geld über die nächsten $n$ Tage kommen. Am $i$-ten Tag hat sie zwei Möglichkeiten:

  • In der Mensa essen, wodurch sie eine Zufriedenheit von $a_i$ erhält und $b_i$ Yuan ausgibt.
  • Mit ihren Teamkollegen auswärts essen gehen, wodurch sie eine Zufriedenheit von $c_i$ erhält und $d_i$ Yuan ausgibt.

Da A und B jeden Tag auswärts essen gehen, fallen jeden Tag Taxikosten an. Sei $e_i$ der Taxifahrpreis am $i$-ten Tag; die drei haben folgende Regel für das Bezahlen des Taxis aufgestellt:

  • Wenn Grammy am $i$-ten Tag nicht auswärts essen geht, bezahlt A mit einer Wahrscheinlichkeit von $\frac{p_i}{100}$ das Taxi, und B bezahlt mit einer Wahrscheinlichkeit von $(1 - \frac{p_i}{100})$.
  • Wenn Grammy am $i$-ten Tag auswärts essen geht und seit dem letzten Mal, als Grammy das Taxi bezahlt hat (oder seit dem ersten Tag, falls Grammy noch nie das Taxi bezahlt hat), sowohl A als auch B jeweils mindestens einmal das Taxi bezahlt haben (unabhängig davon, ob Grammy zu diesem Zeitpunkt mitgegangen ist), dann muss Grammy diesmal das Taxi bezahlen. Andernfalls bezahlt einer der Teamkollegen gemäß der vorherigen Regel.

Jeden Tag wählt Grammy ihre Aktion vor dem Essen. Sie weiß, wer am Vortag das Taxi bezahlt hat, und ihr Ziel ist es, den Erwartungswert der Gesamtzufriedenheit zu maximieren und gleichzeitig sicherzustellen, dass die Gesamtausgaben im schlimmsten Fall $m$ Yuan nicht überschreiten. Wenn sie jeden Tag optimale Entscheidungen trifft, wie groß ist dann der Erwartungswert der Gesamtzufriedenheit?

Eingabe

In jeder Testdatei gibt es nur einen einzigen Testfall.

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), die die Anzahl der Tage und das Gesamtausgabenlimit angeben.

In den folgenden $n$ Zeilen enthält die $i$-te Zeile sechs ganze Zahlen $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ und $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$). Ihre Bedeutungen sind oben beschrieben.

Ausgabe

Gib eine Zeile mit einer einzigen Zahl aus, die den maximalen Erwartungswert der Gesamtzufriedenheit angibt. Falls kein Plan existiert, bei dem die Gesamtausgaben im schlimmsten Fall höchstens $m$ Yuan betragen, gib $-1$ aus.

Deine Antwort wird als korrekt gewertet, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet. Formal ausgedrückt: Sei $a$ deine Ausgabe und $b$ die Antwort der Jury, dann wird deine Ausgabe genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ gilt.

Beispiele

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.