Universal Cup Judging System

Universal Cup

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

Grammy 有兩位隊友 A 和 B。通常這兩位隊友每天都會外出到高級餐廳用餐,而 Grammy 一般都在學校餐廳吃飯。在學校餐廳吃飯省時又省錢,而外出用餐有時還會產生計程車車資。即便如此,Grammy 有時仍會選擇與隊友一起外出用餐以改善伙食。

隨著月底將近,Grammy 的生活費只剩下 $m$ 元,她需要用這筆錢度過接下來的 $n$ 天。在第 $i$ 天,她有兩種選擇:

  • 在學校餐廳吃飯,獲得 $a_i$ 的滿足感並花費 $b_i$ 元。
  • 與隊友外出用餐,獲得 $c_i$ 的滿足感並花費 $d_i$ 元。

由於 A 和 B 每天都會外出用餐,因此每天都會有計程車車資。設第 $i$ 天的計程車車資為 $e_i$,她們三人制定了支付計程車車資的規則:

  • 如果 Grammy 在第 $i$ 天沒有外出用餐,則有 $\frac{p_i}{100}$ 的機率由 A 支付計程車車資,並有 $(1 - \frac{p_i}{100})$ 的機率由 B 支付。
  • 如果 Grammy 在第 $i$ 天外出用餐,且自從上次 Grammy 支付計程車車資以來(若 Grammy 從未支付過計程車車資,則自第一天以來),A 和 B 各自都至少支付過一次計程車車資(無論當時 Grammy 是否一起外出用餐),那麼這次就由 Grammy 支付計程車車資。否則,將由其中一位隊友按照前一條規則支付。

每天用餐前,Grammy 都會選擇她的行動。她會知道前一天是由誰支付計程車車資,而她的目標是在確保最壞情況下總花費不超過 $m$ 元的前提下,最大化總滿足感的期望值。如果她每天都做出最佳決策,總滿足感的期望值為何?

輸入格式

每個測試檔案中只有一組測試資料。

第一行包含兩個整數 $n$ 與 $m$($1 \le n \le 2 \times 10^3$,$1 \le m \le 5 \times 10^3$),分別代表天數與總花費上限。

接下來的 $n$ 行中,第 $i$ 行包含六個整數 $a_i$、$b_i$、$c_i$、$d_i$、$e_i$ 與 $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$)。其意義如題目敘述所示。

輸出格式

輸出一行包含一個數值,代表總滿足感的最大期望值。若不存在任何方案能使最壞情況下的總花費小於或等於 $m$ 元,請輸出 $-1$。

若你的答案之絕對誤差或相對誤差不超過 $10^{-6}$,則視為正確。形式化地說,假設你的輸出為 $a$,而裁判的答案為 $b$,若且唯若 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 時,你的輸出會被接受。

範例

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.