Problem AC
Bastubad
Languages
en
ja
sv
I sÀllskap uppstÄr dock ofta problem. Det viktigaste nÀr man badar bastu Àr att temperaturen sÀtts rÀtt. En finlÀndare Àr vÀldigt petig med bastuns temperatur. Olika finlÀndare har olika högstatemperaturer som de tolererar. Om temperaturen Àr för hög för en viss finlÀndare sÄ gÄr finlÀndaren hem. I temperaturintervallet som en viss finlÀndare klarar blir finlÀndaren dessutom olika glad beroende pÄ temperaturen. En finlÀndares glÀdje ges av en kvadratisk funktion (pÄ formen $ax^2 + bx + c$).
Ett stort sÀllskap finlÀndare ska nu bada bastu, och behöver din hjÀlp. Kan du bestÀmma den maximala summan av finlÀndarnas glÀdje, om bastuns temperatur sÀtts optimalt? Om temperaturen sÀtts högre Àn vad en finne tolererar, sÄ bidrar inte denna finne till den totala glÀdjen alls (den har ju gÄtt hem). Temperaturen anges i kelvin, med en undre grÀns pÄ $0 \textrm{ K}$ och övre grÀns $100\, 000 \textrm{ K}$.
Indata
Den första raden innehÄller ett heltal $1 \le N \le 100\, 000$: antalet finlÀndare. DÀrefter följer $N$ rader, en per finlÀndare. Varje rad innehÄller fyra heltal $a, b, c, t$ ($-10^9 \le a,b,c \le 10^9, 1 \le t \le 100\, 000$), vilket representerar att finlÀndaren har glÀdjefunktion $ax^2 + bx + c$, and bara klarar av temperaturer mellan $0\textrm{ K}$ och $t\textrm{ K}$, inklusive. Funktionen garanteras vara positiv överallt mellan $0$ och $t$.
Utdata
Skriv ut ett enda tal: den största möjliga lycka som kan uppnÄs om temperaturen sÀtts rÀtt. Svaret kommer accepteras om det har ett relativt eller absolut fel om högst $10^{-5}$.
PoÀngsÀttning
Din lösning kommer att testas pÄ en mÀngd testfallsgrupper. För att fÄ poÀng för en grupp sÄ mÄste du klara alla testfall i gruppen.
|
Grupp |
PoÀngvÀrde |
GrÀnser |
|
$1$ |
$21$ |
$N \le 1000$, alla $t$ Àr samma. |
|
$2$ |
$29$ |
$N \le 1000$, alla $a$ Àr positiva (d.v.s., finnarna gillar temperaturextremer). |
|
$3$ |
$38$ |
$N \le 1000$, alla $a$ Àr negativa. |
|
$4$ |
$12$ |
Inga begrÀnsningar. |
Förklaring av exempel $1$
I detta fall Àr den optimala temperaturen $0 \textrm{ K}$. BÄda finnar har i detta fall samma glÀdje: $1 \cdot 0^2 -6\cdot 0 + 10 = 10$. Deras totala glÀdje blir $10 + 10 = 20$.
Förklaring av exempel $2$
I detta fall Àr den optimala temperaturen $\frac{10}{3} \textrm{ K}$. Den första finnens lycka blir $-3(\frac{10}{3})^2 + 20 \cdot \frac{10}{3} + 3 = -\frac{100}{3} + \frac{200}{3} + 3 = 36 + \frac{1}{3}$. Den andra finnen gÄr i detta fallet hem för att temperaturen Àr för hög (hon tolererar bara temperaturer upp till $1\textrm{ K}$). Den totala lyckan blir dÀrmed $36 + \frac{1}{3}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 -6 10 4 1 -6 10 7 |
20.0000000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 -3 20 3 5 -1 0 2 1 |
36.3333333333 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 1000000 2 3 10000 |
100000000020003.0000000000 |
