Informatică, întrebare adresată de Utilizator anonim, 9 ani în urmă

Cerința
Gigel are o livadă împărțită în nm 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

102
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.Cerința
Gigel are o livadă împărțită în nm 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

102

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.

Răspunsuri la întrebare

Răspuns de sfechisalin

Solutia de 100p,bafta !

Anexe:

sfechisalin: #include <cstdio>
using namespace std;
int a[1005][1005],n,m,k,a1,b,c,d,s,smax;
int af,bf,cf,df;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int i1=1;i1<=m;i1++) scanf("%d",&a[i][i1]);
for(int i=1;i<=k;i++)
{
scanf("%d%d%d%d",&a1,&b,&c,&d);
if(!(a1>=af)||!(b>=bf)||!(c<=cf)||!(d<=df))
{s=0;
for(int i=a1;i<=c;i++)
for(int i1=b;i1<=d;i1++) s+=a[i][i1];
if(s>smax) {smax=s;af=a1;bf=b;cf=c;df=d;}}
}
printf

sfechisalin: printf("%d",smax);

scoicadelac: am luat 100

scoicadelac: ultumesc

sfechisalin: ok,vezi ca prima mea solutie e de la CIrese1,tu ai luat 60p pe problema Cirese,poti sa pui si Cirese1 si obtii 100p pe prima sursa.

sfechisalin: Oricum,eu am rezolvat problema Cirese1 pentruca ,tu pe asta o ai aici,din intamplare aveam rezolvata si problema Cirese.

scoicadelac: aaaaah ............

scoicadelac: Am inteles

scoicadelac: multumesc x2

sfechisalin: Cu placere :D

Întrebarea anterioară

Următoarea întrebare

Alte întrebări interesante