Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Grammy มีเพื่อนร่วมทีมสองคนคือ A และ B โดยปกติแล้วเพื่อนร่วมทีมทั้งสองจะออกไปกินข้าวที่ร้านอาหารดีๆ ทุกวัน ในขณะที่ Grammy มักจะกินข้าวที่โรงอาหารของมหาวิทยาลัย การกินที่โรงอาหารช่วยประหยัดเวลาและเงิน ในขณะที่การออกไปกินข้างนอกบางครั้งมีค่าแท็กซี่ ถึงอย่างนั้น ก็มีบางครั้งที่ Grammy เลือกที่จะออกไปกินข้าวกับเพื่อนร่วมทีมเพื่อเพิ่มคุณภาพมื้ออาหารของเธอ

เมื่อใกล้ถึงสิ้นเดือน Grammy เหลือเงินค่าครองชีพเพียง $m$ หยวน และเธอต้องใช้ชีวิตในอีก $n$ วันถัดไปด้วยเงินจำนวนนี้ ในวันที่ $i$ เธอมีสองทางเลือก:

  • กินที่โรงอาหาร ได้รับความพึงพอใจ $a_i$ และจ่ายเงิน $b_i$ หยวน
  • ออกไปกินข้าวกับเพื่อนร่วมทีม ได้รับความพึงพอใจ $c_i$ และจ่ายเงิน $d_i$ หยวน

เนื่องจาก A และ B ออกไปกินข้าวข้างนอกทุกวัน จึงมีค่าแท็กซี่ในทุกๆ วัน ให้ $e_i$ เป็นค่าแท็กซี่ในวันที่ $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.