Nosaukums
Apakštaisnstūri (rect)
Laika limits
0.60s
Atmiņas limits
256.0 MB
Grūtība
40%

Definīcija

N×M rūtiņas liela tabula aizpildīta ar veseliem nenegatīviem skaitļiem. Nepieciešams noteikt, cik veidos šajā tabulā iespējams atrast taisnstūrveida rūtiņu apgabalu, kura rūtiņās ierakstīto skaitļu summa būtu vismaz A, bet nepārsniegtu B (A un B - veseli nenegatīvi skaitļi, A≤B). Taisnstūrveida apgabals var būt arī viena atsevišķa rūtiņa vai visa tabula.

Uzrakstiet programmu, kas atrod aprakstīto taisnstūru skaitu!


Ievaddatu raksturojums

Pirmajā rindā dotas veselu nenegatīvu skaitļu N (tabulas rindu skaits, 1≤N≤300), M (tabulas kolonnu skaits, 1≤M≤300), A (mazākā pieļaujamā summas vērtība) un B (lielākā pieļaujamā summas vērtība, A≤B≤2×109 ). Katri divi blakus skaitļi ir atdalīti ar tukšumzīmi. Nākamajās N rindās dots tabulas rūtiņās ierakstīto skaitļu apraksts. Katrā no šīm rindām doti M veseli nenegatīvi skaitļi, kur katri divi blakus skaitļi atdalīti ar tukšumzīmi. Katram n(1≤n≤N) un m(1≤m≤M) skaitlis ievaddatu n+1-ās rindas m-tais skaitlis pēc kārtas ir ierakstīts tabulas n-tās rindas m-tās kolonnas rūtiņā. Zināms, ka tabulā ierakstīto skaitļu kopsumma nepārsniedz 2×109 .


Izvaddatu raksturojums

Vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - derīgo taisnstūrveida apgabalu skaits


Piezīmes

Uzdevums no: LATVIJAS 31.INFORMĀTIKAS NOVADA OLIMPIĀDES VECĀKĀS (11.-12. KLAŠU) GRUPAS


Paraugdati

Stdin
3 4 7 9
1 0 2 3
6 7 0 3
3 0 4 2
Stdout
13

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.