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.