| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 11 | 5 | 3 | 60.000% |
Histogram je grafički prikaz statističke distribucije — funkcije koja svakom cijelom broju j između 1 i n pridružuje određenu vrijednost hj. 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.
Slika 1: Histogram iz prvog primjera test podataka te sva tri moguća pravokutnika.
Zadan je histogram i prirodan broj p, odredite broj različitih pravokutnika R za koje vrijedi: vrhovi od R su točke s cjelobrojnim koordinatama, jedna stranica od R leži na x-osi, unutrašnjost od R je potpuno pokrivena histogramom i površina od R je barem p.
U prvom redu nalaze se prirodni brojevi n i p — širina histograma i najmanja dozvoljena površina pravokutnika. U sljedećem redu nalazi se n prirodnih brojeva h1, h2, . . . , hn — vrijednosti distribucije predstavljene histogramom.
Ispišite traženi broj pravokutnika.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | 1 ≤ n ≤ 3 000, 1 ≤ p ≤ 1012, 1 ≤ hi ≤ 109 |
| 2 | 15 | 1 ≤ n ≤ 100 000, 1 ≤ p ≤ 108, 1 ≤ hi ≤ 1 000 |
| 3 | 15 | 1 ≤ n ≤ 100 000, p = 1, 1 ≤ hi ≤ 109 |
| 4 | 25 | 1 ≤ n ≤ 100 000, 1 ≤ p ≤ 100 000, 1 ≤ hi ≤ 109 |
| 5 | 35 | 1 ≤ n ≤ 100 000, 1 ≤ p ≤ 1014, 1 ≤ hi ≤ 109 |
6 9 1 4 4 5 2 3
3
10 5 3 6 1 3 2 1 5 3 4 2
31