Rezolvare PBinfo #4679

PbInfo vă pune la dispoziție câteva lucruri grozave: o matrice de n x n numere naturale, un număr natural k, precum și alte două numere naturale L și H, unde L ≤ H.

Cerința

Trebuie să determinați câte submatrice k x k au suma elementelor cuprinsă între L și H.

Date de intrare

Programul citește de la tastatură numerele n k L H, iar de pe următoarele n linii citește câte n numere naturale reprezentând o linie din matrice.

Date de ieșire

Programul va afișa pe ecran valoarea S, reprezentând câte de submatrice k x k au suma elementelor cuprinsă între L și H.

Restricții și precizări

• 1 ≤ k < n ≤ 500, 0 ≤ L ≤ H ≤ 250.000.000
• numerele din matrice vor fi mai mici decât 1000

Exemplu:

Intrare

3 2 15 20
2 3 4
5 4 7
1 8 9

Ieșire

2

Explicație

Cele două submatrice 2 x 2 care au suma elementelor cuprinsă între 15 și 20 sunt:

3 4
4 7

și

5 4
1 8