#2432
Se consideră o matrice pătratică de dimensiune N, conţinând numere naturale. Numim cruce de lăţime K reuniunea mulțimii tuturor elementelor aflate pe K linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe K coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cruci, în formă de T sau L, când una dintre liniile sau coloanele care formează crucea sunt chiar la marginea matricei. Vom defini valoarea unei cruci ca fiind suma elementelor din care aceasta este formată.
Cerința
Scrieți un program care, pentru o valoare K dată, determină o cruce de lățime K a cărei valoare este maximă și poziția ei în matrice. Această poziție va fi exprimată prin perechea de indici reprezentând prima linie din cele K consecutive și prima coloană din cele K consecutive din care este formată crucea.
Date de intrare
Fişierul cruce.in conţine pe prima linie numerele N şi K, iar pe următoarele N linii câte N numere întregi reprezentând în ordine, pe linii, elementele matricei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
Date de ieșire
Fişierul cruce.out va conţine trei numere Vmax L C, separate prin câte un spaţiu, reprezentând valoarea maximă determinată pentru o cruce de lățime K, respectiv linia și coloana care exprimă poziția acesteia în matrice.
Restricții și precizări
1 ≤ N ≤ 5001 ≤ K < N- Numerele din matrice sunt din intervalul
[-5000, 5000] - Liniile şi coloanele se indexează începând cu
1. - Dacă există mai multe cruci de lățime
Kde valoare maximă, se va lua în considerare poziția cu indicele liniei mai mic, iar în caz de egalitate a liniilor poziția celei cu indicele coloanei mai mic. - La olimpiadă s-au oferit 10 puncte din oficiu, aici vor fi date pe exemple.
Exemplu
cruce.in
5 2 1 -2 3 -1 4 -3 2 2 -2 -1 1 2 3 4 5 1 0 -7 1 1 3 2 1 2 3
cruce.out
23 2 4
Explicație
Elementele ce formează crucea de valoare maxima sunt:
Exemplu
cruce.in
5 2 0 0 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 1 1 1
cruce.out
28 2 3
Explicație
Valoarea maximă a unei cruci de lățime 2 este 28.
În exemplu mai există cruci de valoare 28, dar cu indicele de început al liniei sau coloanei mai mari.
De exemplu crucea care începe de pe linia 3 și coloana 3.
#include <fstream>
using namespace std;
#define M 512
int a[M][M],s[M][M];
int main()
{
int n,i,j,k,s1,mx=-2000000000, imax=0,jmax=0;
ifstream fi("cruce.in"); ofstream fo("cruce.out");
fi>>n>>k;
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
fi>>a[i][j];
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
for (i=1;i<=n-k+1;i++)
for (j=1;j<=n-k+1;j++) {
s1=s[i-1][j+k-1]-s[i-1][j-1]+s[i+k-1][n]-s[i-1][n]+s[n][j+k-1]-s[i+k-1][j+k-1]
-s[n][j-1]+s[i+k-1][j-1];
if (s1>mx) {mx=s1; imax=i; jmax=j;}
}
fo<<mx<<" "<<imax<<" "<<jmax;
return 0;
}