Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Грэммидің A және B деген екі командаласы бар. Әдетте екі командаласы күн сайын жақсы мейрамханаларға барып тамақтанады, ал Грэмми көбінесе мектеп асханасында тамақтанады. Мектеп асханасында тамақтану уақыт пен ақшаны үнемдейді, ал сыртқа шығу кейде такси шығындарын талап етеді. Соған қарамастан, Грэмми тамағын жақсарту үшін кейде командаластарымен бірге сыртқа шығуды таңдайды.

Айдың соңы жақындаған сайын, Грэммидің күнделікті шығындарына тек $m$ юань ғана қалды, және ол осы ақшамен келесі $n$ күнді өткізуі керек. $i$-ші күні оның екі таңдауы бар:

  • Асханада тамақтанып, $a_i$ қанағаттану деңгейін алу және $b_i$ юань жұмсау.
  • Командаластарымен бірге сыртта тамақтанып, $c_i$ қанағаттану деңгейін алу және $d_i$ юань жұмсау.

A мен B күн сайын сыртта тамақтанатындықтан, күн сайын такси ақысы төленеді. $i$-ші күнгі такси ақысын $e_i$ деп белгілейік, үшеуі такси ақысын төлеудің келесі ережесін бекітті:

  • Егер Грэмми $i$-ші күні сыртқа тамақтануға бармаса, онда $\frac{p_i}{100}$ ықтималдықпен такси ақысын A төлейді, ал $(1 - \frac{p_i}{100})$ ықтималдықпен B төлейді.
  • Егер Грэмми $i$-ші күні сыртқа тамақтануға барса, және Грэмми соңғы рет такси ақысын төлегеннен бері (немесе егер Грэмми ешқашан такси ақысын төлемеген болса, бірінші күннен бері) A да, B де такси ақысын кемінде бір-бір реттен төлеген болса (сол кезде Грэмми сыртқа тамақтануға барған-бармағанына қарамастан), онда бұл жолы такси ақысын Грэмми төлейді. Әйтпесе, командаластарының бірі алдыңғы ереже бойынша төлейді.

Күн сайын Грэмми өз әрекетін тамақтанар алдында таңдайды. Ол алдыңғы күні такси ақысын кім төлегенін біледі, және оның мақсаты — ең қолайсыз жағдайда жалпы шығындар $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.