Vikendica

View as PDF

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Dragančetu je dosadilo da živi u gradu pa je rešio da sagradi sebi vikendicu, u kojoj ćeu miru i tišini moći da sprovodi svoje programerske ideje. Kako je Draganče veoma vredan,rešio je da sam napravi nacrte njegove kuće iz snova. No, na početku je trebalo da odredimesto na kome će se graditi. Kako Draganče nije baš bogat (matematika i programiranjenije bilo isplativo kako je on mislio), odredio je maksimalni budžet koji može da potrošiza kupovinu placeva. Naravno, želi da vikendica bude što lepša, pa je odredio i donjugranicu budžeta. Sad je u nedoumici gde da je sagradi. Pomozite Dragančetu da odredi brojmogućih mesta za gradnju vikendice.

Mesta na kojima Draganče može da gradi vikendicu data su u obliku pravougane matrice,gde polja predstavljaju placeve. Za svaki plac je data njegova cena. Vikendica je u oblikupravougaonika. Na pravougaoniku se može sagraditi vikendica ukoliko suma njenih parcelaupada u granice budžeta.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu se nalaze četiribroja: n, m, A i B, koji predstavljaju broj vrsta i kolona matrice, donju granicu i gornjugranicu budžeta. U narednih n redova nalazi se po m nenegativnih celih brojeva koji predstavljaju cene placeva.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu štampatibroj mogućih pozicija vikendice.

Ograničenja:

  • 1 ≤ n, m ≤ 150
  • 0 ≤ AB ≤ 109
  • cene placeva su u opsegu [0, 104]
  • broj rešenja ne prelazi 230
  • ukupna suma cena svih placeva je manja od 230
  • vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

standardni ulaz      standardni izlaz
3 3 2 3
1 0 0
0 1 0
0 0 1
        
7

Objašnjenje:

Moguće pozicije za vikendicu (predstavljene sa 'o') su sledeće:

oox ooo oox xxx xoo xxx ooo
oox ooo oox xoo xoo ooo ooo
xxx xxx oox xoo xoo ooo ooo

Suma elemenata u označenim pravougaonicima je u opsegu [2,3].

Primer 2:

standardni ulaz      standardni izlaz
3 4 7 10
1 3 4 2
3 4 5 2
1 3 4 1
        
16

Comments

There are no comments at the moment.