Question

Poveste
Tocmai ai fost angajat în departamentul de procesare de imagini al unei mari companii. Pentru a te acomoda cu noul loc de muncă, ai primit un task simplu: Vei primi o imagine alb-negru și trebuie să afli pentru diverse zone din imagine care este intensitatea totală de alb din acea zonă.

Imaginea pe care o primești are forma unei matrice mt cu N linii și M coloane. Fiecare element i, j al matricei reprezintă intensitatea pixelului aflat pe linia i și coloana j din imagine.

Managerul tău îți dă G zone din imagine, iar tu trebuie să îi spui pentru fiecare dintre cele G zone, care este intensitatea totală a zonei. Intensitatea totală a unei zone este suma totală a intensităților fiecărui pixel din zonă.

O zonă din imagine este definită prin numerele i1, j1, i2, j2. Zona este de fapt submatricea cu colțul din stânga-sus (i1, j1) și dreapta-jos (i2, j2).

Cerință
Dându-se imaginea și cele G zone, să se afle pentru fiecare zonă intensitatea totală.

Date de intrare
De pe prima linie se citesc de la tastatură numerele N și M. De pe următoarele N linii, se citesc M numere naturale care reprezintă intensitatea fiecărui pixel.

De pe următoarea linie se va citi numărul G, reprezentând numărul de zone din imagine pentru care trebuie să afli intensitatea totală.

Pe fiecare dintre următoarele G linii se vor afla câte 4 numere i1, j1, i2, j2, reprezentând coordonatele submatricei.

Date de ieșire
Programul va afișa pe ecran G linii, reprezentând intensitatea totală a fiecărei zone.

Restricții
1 ≤ N, M ≤ 100
-3 000 ≤ mt[i][j] ≤ 3 000
1 ≤ G ≤ 100
1 ≤ i1 ≤ i2 ≤ N
1 ≤ j1 ≤ j2 ≤ M


Exemplu
Date de intrare
4 5
-1 -1 -4 -4 -1
-1 -1 -5 -5 -1
-1 -1 -1 -9 -1
-1 -6 -7 -8 -1
3
1 1 4 5
3 4 3 4
2 2 3 4


Date de ieșire

-60
-9
-22

Answer 1

#include <iostream>

using namespace std;

int a[101][101], n , m, g;

long long sp[101][101];

int main(){

       cin >> n >> m;

        for(int i=1; i<=n;++i)

               for(int j=1; j<=m;++j)

                       cin>>a[i][j], sp[i][j]= sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+a[i][j];

       cin>>g;

       int i1, j1, i2, j2;

       for(int i=1;i<=g; ++i){

               cin>>i1>>j1>>i2>>j2;

               long long sum=sp[i2][j2]-sp[i2][j1-1]-sp[i1-1][j2]+sp[i1-1][j1-1];

               cout<< sum<<endl;

       }

}