Bastubad
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 + 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}^2 + 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 |
