Eng issiq davr

$n$ kunlik harorat ma'lum: $i$-kuni $a_i$ daraja. Kamida $k$ kun davom etgan ketma-ket kunlar oralig'ining o'rtacha harorati shu oraliqdagi haroratlar yig'indisining kunlar soniga nisbati. Barcha shunday oraliqlar ichida eng katta o'rtacha haroratni toping.

Birinchi qatorda $n$ va $k$ ($1 \le k \le n \le 2000$). Ikkinchi qatorda $n$ ta butun son ($1 \le a_i \le 5000$).

Javobni qisqarmaydigan kasr ko'rinishida chiqaring: p/q, bu yerda $p$ va $q$ — o'zaro tub musbat sonlar. Javob butun bo'lsa ham maxraj yoziladi, masalan 5/1.

Prefiks yig'indi bilan har bir oraliq yig'indisi $O(1)$ da topiladi, demak barcha oraliqlarni ko'rib chiqish $O(n^2)$ — $n = 2000$ da $2 \cdot 10^6$ amal. Ikki kasrni haqiqiy sonlarsiz solishtiring: $\frac{s_1}{l_1} < \frac{s_2}{l_2} \iff s_1 l_2 < s_2 l_1$. Oxirida $p$ va $q$ ni EKUBga bo'ling.

Misolda eng yaxshi oraliq $3, 4, 1$: o'rtacha $8/3$.

Manba: Codeforces, 1003C-masala.