DRŽAVNO NATJECANJE 2014. - Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Medijan niza (ne nužno različitih) cijelih brojeva definiramo kao srednji element u nizu koji se dobije njegovim sortiranjem.

Ukoliko je niz parne duljine, tada medijanom smatramo manji od dva srednja broja nakon sortiranja.

Na primjer, medijani nizova (1), (1, 3), (4, 5, 4), (4, 1, 2, 3) i (5, 4, 1, 2, 3) su redom 1, 1, 4, 2 i 3.

Ako je zadana tablica nenegativnih cijelih brojeva koja se sastoji od R redaka i S stupaca te prirodni broj K, napišite program koji će odrediti broj pravokutnika u tablici takvih da je medijan svih brojeva u tom pravokutniku barem K.

Ulazni podaci

U prvom redu nalaze se tri prirodna broja R, S i K (1 ≤ R ≤ 5 000, 1 ≤ S ≤ 50, 1 ≤ K ≤ 1 000 000 000).

U svakom od sljedećih R redova nalazi se niz od točno S nenegativnih cijelih brojeva odvojenih razmakom.

Svi elementi tablice su nenegativni cijeli brojevi manji ili jednaki 1 000 000 000.

Izlazni podaci

U prvi i jedini redak ispišite broj pravokutnika čiji medijan iznosi barem K.

Primjer zadatka

Ulaz

3 3 5
5 8 1
6 3 4
2 1 4

Izlaz

8

Ulaz

4 4 5
1 2 3 4
1 7 7 2
4 5 6 4
4 3 2 1

Izlaz

21

Ulaz

7 5 5
0 6 5 4 2
8 6 1 7 6
9 2 2 3 3
2 9 1 3 6
2 1 5 5 6
5 0 1 0 1
3 8 6 5 6

Izlaz

93