După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul).

Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii și M coloane pe care îl umple cu valori întregi. Cristina va primi un număr de pătrățele de ciocolată egal cu suma valorilor dintr-un dreptunghi ales de ea.”

Deoarece Cristina este prea bosumflată ca să rezolve această “provocare” și prea obosită ca să-l convingă pe Dan să-i dea ciocolata pur și simplu, vă roagă pe voi să o ajutați. (Poate primiți și voi niște ciocolată dacă rezolvați problema. Poate…)

Cerința

Cunoscându-se configurația caroiajului, determinați numărul maxim de pătrățele de ciocolată pe care Cristina îl poate obține alegând un dreptunghi din matrice, precum și coordonatele celor patru colțuri ale acestuia

Date de intrare

Fișierul ciocolata.in conține pe prima linie două numere naturale N și M reprezentând numărul de linii și numărul de coloane ale caroiajului. Pe următoarele N linii se găsesc câte M valori întregi reprezentând valorile din caroiaj.

Date de ieșire

Fisierul ciocolata.out va conține pe prima linie numărul maxim de pătrățele de ciocolată care se poate obține. Pe a doua linie se vor afla patru numere naturale reprezentând coordonatele colțurilor stânga- sus și dreapta-sus (în această ordine) a dreptunghiului ales. Pe cea de-a treia linie se vor afla tot patru numere naturale reprezentând coordonatele colțurilor stânga-jos și dreapta-jos (în această ordine) a dreptunghiului ales.

Restricții și precizări

1 ≤ N, M ≤ 500
Valorile din caroiaj aparțin intervalului [ -2.000.000.000 , 2.000.000.000 ]
În cazul în care există mai multe dreptunghiuri din care se obține aceeași valoare maximă, se va alege cel cu indicele de linie al colțului stânga-sus minim. În cazul în care există mai multe dreptunghiuri cu această proprietate, se va alege cel ce are și indicele de coloană al colțului stânga-sus minim. Dacă există mai multe soluții cu proprietatea că au colțul stânga-sus cu indicii de linie și de coloană minimi, se va alege cel cu indicele de linie al coltului dreapta-jos minim. Dacă mai rămân soluții multiple, se va alege cel care are și indicele de coloană al colțului dreapta-jos minim.
(schematic: valoare maximă → indice linie stânga-sus minim → indice coloană stânga-sus minim → indice linie dreapta-jos minim → indice coloană dreapta-jos minim )
Se garantează că nici Cristinei și nici lui Dan nu li se va face rău de la ciocolată.

Exemplu

ciocolata.in

5 9
3 4 -12 4 6 7 -9 5 12
0 4 5 7 9 -5 1 1 5
0 98 34 0 1 7 -7 1 1
6 7 8 -9 0 -2 3 5 22
47 62 -31 55 0 -83 23 77 -10

ciocolata.out

362
1 1 1 9
5 1 5 9

Explicație

Dreptunghiul determinat de punctele (1, 1), (1, 9), (5, 1), (5, 9).

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

#include <fstream>
#include <climits>
using namespace std;

#define Nmax 502

ifstream fin ( "ciocolata.in" );
ofstream fout  ( "ciocolata.out" );

int v[Nmax][Nmax];
long long sum[Nmax][Nmax];

int main(){
    int N, M, solx1, soly1, solx2, soly2;

    long long maxx = LLONG_MIN , sol;
    
    fin >> N >> M;

    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= M; ++j )
            fin >> v[i][j];

    for ( int i = 1; i <= M; ++i )
        for ( int j = 1; j <= N; ++j )
            sum[j][i] = sum[j-1][i] + v[j][i];

    int x1, y1, x2, y2;
    for ( int i = 1; i <= N; ++i ){
        x1 = i;
        for ( int j = i; j <= N; ++j ){
            sol = 0;
            x2 = j;
            y1 = 1;
            y2 = 0;
            for ( int k = 1; k <= M; ++k ){
                long long x = sum[j][k] - sum[i-1][k];

                if ( x > sol + x ){
                    y1 = y2 = k;
                    sol = x;
                }
                else{
                    sol = sol + x;
                    y2++;
                }

                if ( sol > maxx ){
                    maxx = sol;
                    solx1 = x1;  solx2 = x2;
                    soly1 = y1;  soly2 = y2;
                }
            }
        }
    }
    
    fout << maxx << "\n";
    fout << solx1 << " " << soly1 << " " << solx1 << " " << soly2 << "\n";
    fout << solx2 << " " << soly1 << " " << solx2 << " " << soly2;
  
    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 #1498 Ciocolata

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