Spákaupmennska á fasteignamarkaði er streituvaldandi vinna með óstöðugar tekjur. Myndi það hjálpa ef þú fengir risastórt lán frá foreldrum þínum og gætir spáð nákvæmlega fyrir um íbúðaverð á völdum dögum?
Þú byrjar án íbúðar, en bankainnistæða þín er $10^{100}$. Þar sem þú ert ekki með fasteignasöluleyfi máttu eiga í mesta lagi eina íbúð í einu. Þú hefur þegar komið auga á ákveðna íbúð á góðum stað, og það er sú sem þú mátt kaupa og síðan selja, mögulega oft.
Fasteignavefurinn MyHouse hefur birt spábil $[a_i, b_i]$ (þar sem $a_i < b_i$) fyrir verð íbúðarinnar næstu $n$ daga. Verð íbúðarinnar á $i$-ta degi er slembin rauntala $c_i$ sem valin er af handahófi með jafnri dreifingu af bilinu $[a_i, b_i]$. Sjálfgefið er að þú fáir að vita verðið $c_i$ í upphafi $i$-ta dags. Þú verður þá að ákveða hvort þú eigir viðskipti. Ef þú átt íbúðina máttu selja hana á $c_i$, og ef þú átt hana ekki máttu kaupa hana á $c_i$.
Aðeins í dag (fyrir fyrsta daginn) leyfir MyHouse-vefurinn nýjum notendum að fá að vita nákvæm verð $c_i$ fyrir valið mengi af $k$ dögum. Það er, þú velur núna mengi af $k$ dögum og færð að vita verð þeirra, en fyrir hvern hinna $n - k$ daganna sem eftir eru færðu að vita verðið í upphafi þess dags.
Eftir $n$ daga verður þú að enda án íbúðar; hagnaður þinn er mismunurinn á loka- og upphafsinnistæðu þinni í bankanum. Ákvarðaðu hámarks væntigildi* hagnaðarins ef þú velur mengið af $k$ dögum ákjósanlega og tekur síðan ákjósanlegar viðskiptaákvarðanir á hverjum hinna $n$ daga.
*Væntigildið er meðalgildi slembibreytu, vegið með líkum. Innsæið segir okkur að það sé útkoman sem búast mætti við að meðaltali þegar slembitilraun er endurtekin oft.
Inntak
Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($0 \le k \le n \le 300\,000$; $1 \le n$), sem tákna annars vegar fjölda daga og hins vegar fjölda verða sem þú mátt fá að vita strax.
Næstu $n$ línur lýsa verðbilum; $i$-ta línan inniheldur tvær heiltölur $a_i$ og $b_i$ ($1 \le a_i < b_i \le 10^6$).
Úttak
Prentaðu eina rauntölu – hæsta mögulega væntigildi hagnaðarins eftir $n$ daga.
Leyfileg hlutfallsleg eða algild skekkja er $10^{-6}$. Það er, ef þú prentar $x$ og rétt nákvæm niðurstaða er $y$, þá verður að gilda að $|x - y| \le 10^{-6} \cdot \max(1, y)$. Þú mátt prenta allt að $20$ aukastafi á eftir kommu.
Dæmi
input
4 0 10 30 10 30 40 50 30 60
output
28.75
input
4 1 10 30 10 30 40 50 30 60
output
31.3888888889
input
6 3 10 50 30 70 50 70 30 50 30 40 10 40
output
33.6805555556
Athugasemd
Í fyrsta prófinu höfum við $k = 0$, þannig að hvert verð fæst uppgefið í upphafi síns dags. Til er ákjósanleg stefna að kaupa íbúðina á degi $1$ eða $2$ með væntum kostnaði upp á $17.5$, og selja hana síðan á degi $3$ eða $4$ með væntum tekjum upp á $46.25$. Væntur hagnaður er $46.25 - 17.5 = 28.75$.
Í öðru prófinu höfum við $k = 1$ og við ættum ákjósanlega að velja dag $4$, svo við fáum strax að vita rauntölu $c_4$ af bilinu $[30, 60]$. Væntur hagnaður er $31\frac{7}{18}$ fyrir ákjósanlegar viðskiptaákvarðanir.
Í þriðja prófinu er ákjósanlegt val á mengi $k$ daga $\{2, 3, 6\}$. Við fáum strax að vita verðin $c_2$, $c_3$ og $c_6$.