Question

Cerința

Intr-o gradina zoologica reprezentata printr-o matrice A cu n linii si m coloane. Fiecare cusca se afla intr-o pozitie din matrice si contine x animale. De exemplu daca A[2][6] = 5 inseamna ca in cusca de pe linia 2 si coloana 6 se afla 5 animale. Sa se raspunda la Q intrebari de forma i1, j1, i2, j2 unde raspunsul va fi numarul de animale din dreptunghiul din matrice cu cordonatele coltului din stanga sus i1 si j1 si cordonatele coltului din dreapta jos i2 si j2, unde i reprezinta linia si j coloana.
Date de intrare

Fișierul de intrare zoo.in conține pe prima linie numerele n si m, separate printr-un spatiu, iar pe urmatoarele n linii, cate m numere, reprezentand matricea. Pe linia n + 2 se afla numarul Q, iar pe urmatoarele Q linii, cate 4 numere (i1 j1 i2 j2) cu semnificatia din enunt.
Date de ieșire

Fișierul de ieșire zoo.out pe fiecare linie i raspunsul la intrebarea i.
Restricții și precizări

1 ≤ n, m ≤ 100
1 ≤ Q ≤ 100000
numarul maxim de animale dintr-o cusca este de 1.000.000.000
numerotarea liniilor si a coloanelor din matrice incepe de la 1

Answer 1

#include <fstream>

using namespace std;

ifstream f("zoo.in");

ofstream g("zoo.out");

int n,m,a[105][105];

long long s[105][105];

int main()

{   f>>n>>m;

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

       for(int j=1; j<=m; j++) f>>a[i][j];

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

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

           s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

   int q;

   f>>q;

   while(q--)

   {   int i1,j1,i2,j2;

       f>>i1>>j1>>i2>>j2;

       g<<s[i2][j2]-s[i2][j1-1]-s[i1-1][j2]+s[i1-1][j1-1]<<'\n';

   }

   return 0;

}