Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Grammy memiliki dua rekan tim, A dan B. Biasanya, kedua rekan tim tersebut pergi makan di restoran bagus setiap hari, sedangkan Grammy umumnya makan di kantin kampus. Makan di kantin kampus menghemat waktu dan uang, sementara makan di luar terkadang membutuhkan ongkos taksi. Meski begitu, ada kalanya Grammy memilih pergi makan bersama rekan timnya untuk menikmati makanan yang lebih enak.

Menjelang akhir bulan, Grammy hanya memiliki sisa uang sebesar $m$ yuan untuk biaya hidupnya, dan ia harus melewati $n$ hari berikutnya dengan uang tersebut. Pada hari ke-$i$, ia memiliki dua pilihan:

  • Makan di kantin, memperoleh kepuasan sebesar $a_i$ dan menghabiskan $b_i$ yuan.
  • Pergi makan di luar bersama rekan timnya, memperoleh kepuasan sebesar $c_i$ dan menghabiskan $d_i$ yuan.

Karena A dan B pergi makan di luar setiap hari, akan selalu ada ongkos taksi setiap harinya. Misalkan $e_i$ adalah ongkos taksi pada hari ke-$i$, mereka bertiga telah menetapkan aturan pembayaran ongkos taksi:

  • Jika Grammy tidak pergi makan di luar pada hari ke-$i$, maka terdapat peluang $\frac{p_i}{100}$ bahwa A yang akan membayar ongkos taksi, dan peluang $(1 - \frac{p_i}{100})$ bahwa B yang akan membayar.
  • Jika Grammy pergi makan di luar pada hari ke-$i$, dan sejak terakhir kali Grammy membayar ongkos taksi (atau sejak hari pertama, jika Grammy belum pernah membayar ongkos taksi), baik A maupun B masing-masing telah membayar ongkos taksi setidaknya satu kali (terlepas dari apakah Grammy ikut makan di luar pada saat itu atau tidak), maka kali ini Grammy yang akan membayar ongkos taksi. Jika tidak, salah satu rekan tim akan membayar sesuai aturan sebelumnya.

Setiap hari, Grammy akan memilih tindakannya sebelum makan. Ia mengetahui siapa yang membayar ongkos taksi pada hari sebelumnya, dan tujuannya adalah memaksimalkan nilai harapan total kepuasan, sambil memastikan bahwa total pengeluaran tidak melebihi $m$ yuan dalam skenario terburuk. Jika ia mengambil keputusan optimal setiap hari, berapakah nilai harapan dari total kepuasan?

Masukan

Hanya terdapat satu kasus uji di setiap berkas uji.

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), yang menyatakan banyaknya hari dan batas total pengeluaran.

Untuk $n$ baris berikutnya, baris ke-$i$ berisi enam bilangan bulat $a_i$, $b_i$, $c_i$, $d_i$, $e_i$, dan $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$). Makna masing-masing variabel telah dijelaskan di atas.

Keluaran

Keluarkan satu baris yang berisi satu bilangan, yang menyatakan nilai harapan maksimum dari total kepuasan. Jika tidak ada rencana yang membuat total pengeluaran kurang dari atau sama dengan $m$ yuan dalam skenario terburuk, keluarkan $-1$.

Jawaban Anda akan dianggap benar jika galat mutlak atau galat relatifnya tidak melebihi $10^{-6}$. Secara formal, misalkan keluaran Anda adalah $a$ dan jawaban juri adalah $b$, keluaran Anda diterima jika dan hanya jika $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Contoh

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.