Histogram
시간 제한1초메모리 제한1024 MB
x축에 한 변이 놓이고 히스토그램 안에 완전히 들어가는 정수 좌표 직사각형 중 넓이가 p 이상인 것의 개수를 센다.
문제
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.