시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 71 | 35 | 35 | 56.452% |
Svakom cijelom broju j između 1 i n pridružen je broj hj. Te brojeve ćemo prikazivati histogramom. Histogram crtamo tako da za svaki broj j nacrtamo stupac širine 1 i visine hj te sve takve stupce uredno posložimo na x-os slijeva nadesno počevši od ishodišta.
Primjeri histograma koji odgovaraju probnim primjerima.
Milan ima jedan takav histogram i na njega želi zalijepiti poster pravokutnog oblika na kojemu je prikazan njegov najveći heroj – gospodin Malnar.
Za pravokutnik kažemo da je pravilno pozicioniran unutar histograma ako mu vrhovi imaju cjelobrojne koordinate, stranice su mu paralelne s koordinatnim osima te je unutrašnjost tog pravokutnika u potpunosti prekrivena histogramom.
Odredite za svaki broj j između 1 i n iznos najveće površine pravokutnika koji se može pravilno pozicionirati unutar prvih j stupaca histograma.
U prvom je retku prirodni broj n (1 ≤ n ≤ 2 · 105), broj stupaca u histogramu.
U sljedećem se retku nalazi n prirodnih brojeva h1, h2, . . . , hn (1 ≤ hi ≤ 107), visine stupaca u histogramu.
U jedini redak ispišite n brojeva, j-ti od tih brojeva predstavlja iznos najveće površine pravokutnika koji se može pravilno pozicionirati unutar prvih j stupaca histograma.
3 2 3 7
2 4 7
5 3 4 2 7 6
3 6 6 8 12