- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on taulukko, jossa on n kokonaislukua. Tehtäväsi on etsiä kussakin kohdassa kyseiseen kohtaan päättyvä alitaulukko, jonka keskiarvo on mahdollisimman suuri.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.
Tämän jälkeen syötteessä on n kokonaislukua a_1,a_2,\ldots,a_n: taulukon sisältö.
Tuloste
Tulosta n kokonaislukua: kussakin kohdassa alitaulukon pituus. Jos mahdollisia alitaulukoita on useita, tulosta niistä pisimmän pituus.
Esimerkki
Syöte:
7 1 6 4 6 2 5 5
Tuloste:
1 1 2 1 4 1 2
Selitys: Tarkastellaan esimerkiksi kohtaa, jossa on luku 2. Tähän kohtaan päättyvät keskiarvot ovat \frac{1+6+4+6+2}{5}=3.8, \frac{6+4+6+2}{4}=4.5, \frac{4+6+2}{3}=4, \frac{6+2}{2}=4 ja \frac{2}{1}=2. Näistä korkein keskiarvo saadaan valitsemalla pituuden 4 alitaulukko.
Osatehtävä 1 (12 pistettä)
- 1 \le n \le 100
- 1 \le a_k \le 10^6
Osatehtävä 2 (17 pistettä)
- 1 \le n \le 5000
- 1 \le a_k \le 10^6
Osatehtävä 3 (71 pistettä)
- 1 \le n \le 10^5
- 1 \le a_k \le 10^6