Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Grammy ma dwóch kolegów z drużyny, A oraz B. Zazwyczaj ci dwaj koledzy codziennie chodzą jeść do dobrych restauracji, podczas gdy Grammy jada przeważnie w szkolnej stołówce. Jedzenie w szkolnej stołówce oszczędza czas i pieniądze, natomiast wyjście na miasto wiąże się czasem z kosztami taksówki. Mimo to zdarza się, że Grammy postanawia wyjść z kolegami z drużyny, aby zjeść lepszy posiłek.

Zbliża się koniec miesiąca i Grammy zostało już tylko $m$ juanów na utrzymanie, za które musi przeżyć kolejne $n$ dni. W $i$-tym dniu ma do wyboru dwie opcje:

  • Zjeść w stołówce, zyskując satysfakcję $a_i$ i wydając $b_i$ juanów.
  • Wyjść na posiłek z kolegami z drużyny, zyskując satysfakcję $c_i$ i wydając $d_i$ juanów.

Ponieważ A i B wychodzą na posiłek każdego dnia, codziennie pojawiają się koszty taksówki. Niech $e_i$ oznacza koszt taksówki w $i$-tym dniu; cała trójka ustaliła następującą zasadę płacenia za taksówkę:

  • Jeśli Grammy nie wychodzi jeść w $i$-tym dniu, to z prawdopodobieństwem $\frac{p_i}{100}$ za taksówkę zapłaci A, a z prawdopodobieństwem $(1 - \frac{p_i}{100})$ zapłaci B.
  • Jeśli Grammy wychodzi jeść w $i$-tym dniu, a od ostatniego razu, gdy Grammy płaciła za taksówkę (lub od pierwszego dnia, jeśli Grammy nigdy jeszcze nie płaciła za taksówkę), zarówno A, jak i B zapłacili za taksówkę co najmniej po jednym razie (niezależnie od tego, czy Grammy wówczas wychodziła z nimi jeść), to tym razem za taksówkę płaci Grammy. W przeciwnym razie zapłaci jeden z kolegów zgodnie z poprzednią zasadą.

Każdego dnia Grammy wybiera swoją decyzję przed posiłkiem. Wie, kto zapłacił za taksówkę poprzedniego dnia, a jej celem jest zmaksymalizowanie wartości oczekiwanej łącznej satysfakcji, przy jednoczesnym zagwarantowaniu, że w najgorszym przypadku łączne wydatki nie przekroczą $m$ juanów. Jaka jest wartość oczekiwana łącznej satysfakcji, jeśli każdego dnia podejmuje ona optymalne decyzje?

Wejście

W każdym pliku testowym znajduje się tylko jeden przypadek testowy.

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), oznaczające liczbę dni oraz limit łącznych wydatków.

W kolejnych $n$ wierszach $i$-ty wiersz zawiera sześć liczb całkowitych $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ oraz $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$). Ich znaczenie opisano powyżej.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę, oznaczającą maksymalną wartość oczekiwaną łącznej satysfakcji. Jeśli nie istnieje plan, w którym łączne wydatki w najgorszym przypadku są mniejsze lub równe $m$ juanom, wypisz $-1$.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-6}$. Formalnie, niech Twoja odpowiedź wynosi $a$, a odpowiedź jury wynosi $b$; Twoja odpowiedź zostanie zaakceptowana wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Przykład

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.