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 có hai người đồng đội là A và B. Thông thường, hai người đồng đội ngày nào cũng ra ngoài ăn ở những nhà hàng ngon, còn Grammy thường ăn tại căng tin trường. Ăn ở căng tin trường giúp tiết kiệm thời gian và tiền bạc, trong khi ra ngoài ăn đôi khi lại tốn thêm tiền taxi. Dù vậy, đôi lúc Grammy vẫn chọn đi ăn ngoài cùng đồng đội để cải thiện bữa ăn.

Khi cuối tháng đến gần, Grammy chỉ còn lại $m$ nhân dân tệ cho chi phí sinh hoạt, và cô cần xoay sở trong $n$ ngày tiếp theo với số tiền này. Vào ngày thứ $i$, cô có hai lựa chọn:

  • Ăn ở căng tin, nhận được độ hài lòng $a_i$ và tốn $b_i$ nhân dân tệ.
  • Đi ăn ngoài cùng đồng đội, nhận được độ hài lòng $c_i$ và tốn $d_i$ nhân dân tệ.

Vì A và B đi ăn ngoài mỗi ngày nên ngày nào cũng phát sinh tiền taxi. Gọi $e_i$ là tiền taxi vào ngày thứ $i$, cả ba người đã đặt ra quy tắc trả tiền taxi như sau:

  • Nếu Grammy không đi ăn ngoài vào ngày thứ $i$, thì có xác suất $\frac{p_i}{100}$ là A sẽ trả tiền taxi, và xác suất $(1 - \frac{p_i}{100})$ là B sẽ trả.
  • Nếu Grammy đi ăn ngoài vào ngày thứ $i$, và kể từ lần gần nhất Grammy trả tiền taxi (hoặc kể từ ngày đầu tiên nếu Grammy chưa từng trả tiền taxi), cả A và B mỗi người đều đã trả tiền taxi ít nhất một lần (bất kể lúc đó Grammy có đi ăn ngoài hay không), thì lần này Grammy sẽ trả tiền taxi. Ngược lại, một trong hai đồng đội sẽ trả theo quy tắc phía trên.

Mỗi ngày, Grammy sẽ chọn hành động của mình trước bữa ăn. Cô sẽ biết ai đã trả tiền taxi vào ngày hôm trước, và mục tiêu của cô là tối đa hóa kỳ vọng tổng độ hài lòng, đồng thời đảm bảo tổng chi phí không vượt quá $m$ nhân dân tệ trong trường hợp xấu nhất. Nếu ngày nào cô cũng đưa ra quyết định tối ưu, giá trị kỳ vọng của tổng độ hài lòng là bao nhiêu?

Dữ liệu vào

Mỗi tệp dữ liệu chỉ có duy nhất một bộ dữ liệu.

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), biểu thị số ngày và giới hạn tổng chi phí.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa sáu số nguyên $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ và $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$). Ý nghĩa của chúng đã được mô tả ở trên.

Dữ liệu ra

In ra một dòng chứa một số duy nhất, biểu thị giá trị kỳ vọng lớn nhất của tổng độ hài lòng. Nếu không tồn tại kế hoạch nào đảm bảo tổng chi phí nhỏ hơn hoặc bằng $m$ nhân dân tệ trong trường hợp xấu nhất, hãy in ra $-1$.

Câu trả lời của bạn được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$. Cụ thể, giả sử kết quả của bạn là $a$ và đáp án của ban giám khảo là $b$, kết quả của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Ví dụ

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.