Într-o pădure există plantați copaci pe N linii și M coloane. Copacii au diferite înălțimi. O zonă dreptunghiulară de copaci din cadrul pădurii trebuie tăiată. Pădurarul trebuie să aleagă dintre C zone, o zonă în care suma înălțimilor copacilor este maximă. Deoarece pădurarului îi plac numerele prime, el va alege o zonă în care suma înălțimilor copacilor este și un număr prim.

Cerința

Determinați suma din enunț pentru zonele puse la dispoziție.

Date de intrare

Fișierul de intrare padure.in conţine pe prima linie numerele N, M și C cu semnificația din enunț, pe următoarele N linii înălțimile copacilor, câte M pe o linie, separate prin câte un spațiu, iar pe următoarele C linii, câte patru pe fiecare linie, valorile l1, c1, l2, c2 separate prin câte un spațiu, ce reprezintă coordonatele colțului stânga-sus, respectiv coordonatele colțului dreapta-jos a unei zone ce poate fi tăiată.

Date de ieșire

Fișierul de ieșire padure.out va conţine pe prima linie rezultatul corespunzător cerinței problemei.

Restricții și precizări

1 <= N, M <= 100
1 <= C <= 100000
numerotarea liniilor și coloanelor din pădure începe de la 1
0 < l1 <= l2 <= N
0 < c1 <= c2 <= M
pentru fiecare set de date de intrare există soluție
înălțimea copacilor nu depășește valoarea 100

Exemplu

padure.in

padure.out

Explicație

9 3 2
6 2 1
2 3 2
are suma 30, dar nu este prim
2 1 5
3 2 4
5 3 4
are suma 29

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 padure:

//Cretu Constantin
#include <fstream>

using namespace std;
ifstream fin("padure.in");
ofstream fout("padure.out");
int n,m,c,l1,c1,l2,c2,i,j,k,s,smax;
int a[102][102];
int prim(int x)
{
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        return 0;
    return x>1;
}
int main()
{
    fin>>n>>m>>c;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>a[i][j];
            a[i][j]=a[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1];
        }//a[i][j] este suma tuturor elementelor din zona determinata de primul element si cel curent

    for(k=0;k<c;k++)
    {
        fin>>l1>>c1>>l2>>c2;
        s=a[l2][c2]-a[l2][c1-1]-a[l1-1][c2]+a[l1-1][c1-1];//suma tuturor elementelor din zona determ de elem a[l1][c1] si a[l2][c2]
        if(s>smax)
            if(prim(s))
            smax=s;
    }

    fout<<smax;
    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 #2353 padure

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2353 padure 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 #2353 padure