Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Grammy には A と B という 2 人のチームメイトがいます。普段、2 人のチームメイトは毎日素敵なレストランへ外食に行きますが、Grammy はたいてい学校の食堂で食事をします。学校の食堂で食べると時間とお金を節約できますが、外食するとタクシー代がかかることがあります。それでも、食事を充実させるために Grammy がチームメイトと一緒に外食を選ぶこともあります。

月末が近づき、Grammy の生活費は残り $m$ 元しかなく、このお金で次の $n$ 日間を過ごさなければなりません。$i$ 日目には、彼女には 2 つの選択肢があります:

  • 食堂で食事をし、満足度 $a_i$ を得て $b_i$ 元を支払う。
  • チームメイトと外食し、満足度 $c_i$ を得て $d_i$ 元を支払う。

A と B は毎日外食するため、毎日タクシー代が発生します。$i$ 日目のタクシー代を $e_i$ とすると、3 人はタクシー代の支払いについて次のルールを定めています:

  • $i$ 日目に Grammy が外食しない場合、確率 $\frac{p_i}{100}$ で A がタクシー代を支払い、確率 $(1 - \frac{p_i}{100})$ で B が支払う。
  • $i$ 日目に Grammy が外食し、かつ Grammy が最後にタクシー代を支払ってから(Grammy が一度もタクシー代を支払ったことがない場合は 1 日目から)、A と B の両方がそれぞれ少なくとも 1 回ずつタクシー代を支払っている場合(そのときに Grammy が外食したかどうかは問わない)、今回は Grammy がタクシー代を支払う。そうでない場合は、前のルールに従ってチームメイトの 1 人が支払う。

毎日、Grammy は食事の前に自分の行動を選択します。彼女は前日に誰がタクシー代を支払ったかを知っており、最悪のケースでも総支出が $m$ 元を超えないことを保証しつつ、総満足度の期待値を最大化することが目標です。彼女が毎日最適な判断を下すとき、総満足度の期待値はいくらになりますか?

入力

各テストファイルには 1 つのテストケースのみが含まれます。

1 行目には日数と総支出の上限を表す 2 つの整数 $n$ と $m$($1 \le n \le 2 \times 10^3$、$1 \le m \le 5 \times 10^3$)が与えられます。

続く $n$ 行のうち $i$ 行目には、6 つの整数 $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$)が与えられます。それぞれの意味は上記の通りです。

出力

総満足度の最大期待値を表す 1 つの数値を 1 行に出力してください。最悪のケースで総支出が $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.