Cerința

Gigel are o livadă împărțită în n*m sectoare, dispuse pe n linii, numeroate de la 1 la n și m coloane, numerotate de la 1 la m. În fiecare sector se află un cireș, care conține o cantitate de cireșe cunoscută. Gigel va culege toate cireșele din cireșii dispuși într-o zonă dreptunghiulară din livadă. El poate să aleagă între k zone și dorește să culeagă cât mai multe cireșe.

Scrieți un program care determină cantitatea maximă de cireșe pe care o poate culege Gigel din una dintre cele k zone date.

Date de intrare

Programul citește de la tastatură numerele n m k, cu semnificația de mai sus. Apoi citește cantitatea de cireșe din fiecare sector, linie cu linie. Apoi citește k perechi de coordonate i1 j1 i2 j2, unde i1 j1 reprezintă coordonatele (linie coloana) ale colțului stânga-sus al zonei curente, iar i2 j2 reprezintă coordonatele (linie coloana) ale colțului dreapta-jos al zonei curente.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând cantitatea maximă de cireșe care poate fi culeasă din una dintre zonele date.

Restricții și precizări

1 ≤ n , m ≤ 1000
1 ≤ k ≤ 10000
cantitatea de cireșe din fiecare sector este un număr natural mai mic decât 10000
1 ≤ i1 ≤ i2 ≤ n
1 ≤ j1 ≤ j2 ≤ m
dacă ați rezolvat problema #Cirese ați observat deja că acum livada este mai mare, iar Gigel are mai multe variante de a alege zona din care să culeagă cireșele.

Exemplu

Intrare

4 6 3
3 1 10 7 5 2 
1 5 3 8 6 3 
10 1 3 8 10 8 
6 1 8 3 9 1 
2 2 3 5
1 2 4 6
2 1 4 3

Ieșire

Explicație

Cantitatea de cireșe care pot fi culese din zona a doua este 102 și este mai mare decât cantitățile din celelalte două zone.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cirese1:

#include <iostream>
using namespace std;

int n,m,k,a[1001][1001];
int s[1001][1001];

int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> a[i][j];
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    long long int Max = 0;
    for(int p = 1 ; p < k ; p ++)
    {
        int i1,j1,i2,j2;
        cin >> i1 >> j1 >> i2 >> j2;
        int SC = s[i2][j2] - s[i1-1][j2] - s[i2][j1-1] + s[i1-1][j1-1];
        if(SC > Max)
            Max = SC;
    }
    cout << Max << endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #765 Cirese1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #765 Cirese1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #765 Cirese1