Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

Grammy á tvo liðsfélaga, A og B. Venjulega fara liðsfélagarnir tveir út að borða á góðum veitingastöðum á hverjum degi, en Grammy borðar yfirleitt í mötuneyti skólans. Að borða í mötuneyti skólans sparar tíma og peninga, en að fara út að borða hefur stundum í för með sér leigubílakostnað. Engu að síður kemur fyrir að Grammy ákveður að fara út með liðsfélögum sínum til að gera vel við sig í mat.

Þegar líður að mánaðamótum á Grammy aðeins $m$ júan eftir fyrir framfærslu sinni og hún þarf að láta þessa peninga duga næstu $n$ daga. Á $i$-ta degi hefur hún um tvennt að velja:

  • Borða í mötuneytinu, fá ánægju upp á $a_i$ og eyða $b_i$ júönum.
  • Fara út að borða með liðsfélögum sínum, fá ánægju upp á $c_i$ og eyða $d_i$ júönum.

Þar sem A og B fara út að borða á hverjum degi fellur til leigubílakostnaður á hverjum degi. Látum $e_i$ vera leigubílagjaldið á $i$-ta degi; þau þrjú hafa sett sér reglu um greiðslu leigubílsins:

  • Ef Grammy fer ekki út að borða á $i$-ta degi eru líkurnar $\frac{p_i}{100}$ á að A borgi leigubílinn og líkurnar $(1 - \frac{p_i}{100})$ á að B borgi.
  • Ef Grammy fer út að borða á $i$-ta degi, og síðan Grammy borgaði síðast fyrir leigubílinn (eða frá fyrsta degi ef Grammy hefur aldrei borgað fyrir leigubílinn) hafa bæði A og B borgað fyrir leigubílinn að minnsta kosti einu sinni hvort (óháð því hvort Grammy fór út að borða í það skiptið), þá mun Grammy borga fyrir leigubílinn í þetta sinn. Annars borgar annar liðsfélaganna samkvæmt fyrri reglunni.

Á hverjum degi velur Grammy hvað hún gerir fyrir máltíðina. Hún veit hver borgaði leigubílinn daginn áður og markmið hennar er að hámarka væntigildi heildaránægjunnar, um leið og hún tryggir að heildarútgjöldin fari ekki yfir $m$ júan í versta falli. Ef hún tekur bestu mögulegu ákvarðanir á hverjum degi, hvert er þá væntigildi heildaránægjunnar?

Inntak

Það er aðeins eitt prófunartilvik í hverri prófunarskrá.

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), sem tákna fjölda daga og hámark heildarútgjalda.

Í næstu $n$ línum inniheldur $i$-ta línan sex heiltölur $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ og $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$). Merking þeirra er lýst hér að ofan.

Úttak

Prentið eina línu sem inniheldur eina tölu sem táknar mesta mögulega væntigildi heildaránægju. Ef engin áætlun er til þar sem heildarútgjöldin verða minni en eða jöfn $m$ júönum í versta falli skal prenta $-1$.

Svarið þitt telst rétt ef algild eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$. Formlega séð, ef úttakið þitt er $a$ og svar dómnefndar er $b$, þá er úttakið þitt samþykkt ef og aðeins ef $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Dæmi

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.