| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 5 | 4 | 4 | 80.000% |
Finländare älskar att bada bastu. Det är inte så konstigt egentligen. Bastubadande är både skönt och sker oftast i trevligt sällskap.
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}$.
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$.
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}$.
2 1 -6 10 4 1 -6 10 7
20.0000000000
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$.
2 -3 20 3 5 -1 0 2 1
36.3333333333
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}$.
1 1000000 2 3 10000
100000000020003.0000000000
Olympiad > Swedish Olympiad in Informatics > 2017 > Final C번