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.
  

  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).

  #include <bits/stdc++.h>
  using namespace std;
  
  ifstream cin("ciocolata.in");
  ofstream cout("ciocolata.out");
  
  long long a[501][501] , n , m, s[501][501], smax, x1, y1, lx, ly;
  int main()
  {
      cin >> n >> m;
      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];
  
      long long s1, sum = 0, lasty;
      for (int p = 1; p <= n; p ++)
          for (int q = p; q <= n; q ++)
          {
              sum = 0;
              lasty = 1;
              for (int j = 1; j <= m; j ++)
              {
                  s1 = s[q][j] - s[p - 1][j];
                  sum += s1;
                  if (sum < 0)
                  {
                      sum = 0;
                      lasty = j + 1;
                  }
                  if (sum > smax)
                  {
                      smax = sum;
                      x1 = p;
                      y1 = lasty;
                      lx = q - p;
                      ly = j - lasty;
                  }
              }
          }
      cout << smax << '\n';
      cout << x1 << ' ' << y1 << ' ';
      cout << x1 << ' ' << y1 + ly << '\n';
      cout << x1 + lx << ' ' << y1 << ' ';
      cout << x1 + lx << ' ' << y1 + ly << ' ';
      return 0;
  }

  Comentarii