Într-o matrice pătratică, pentru fiecare poziție identificată prin linia i și coloana j, se adună toate elementele care se găsesc pe linia i sau pe coloana j sau pe diagonalele care trec prin a[i][j] și sunt paralele cu diagonala principală sau cu diagonala secundară, cu precizarea că în această sumă, elementul a[i][j] apare o singură dată.

Cerința

Să se determine suma maximă care se obține prin procedeul prezentat mai sus precum și poziția corespunzătoare (linia și coloana) sumei maxime. Dacă există mai multe poziţii pentru care se obţine suma maximă, se va alege prima dintre acestea, în ordinea parcurgerii matricei pe linii.

Date de intrare

Fișierul de intrare suma7.in conține pe prima linie un număr natural n. Pe fiecare din următoarele n linii se găsesc câte n numere întregi, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire suma7.out va conține pe prima linie valoarea maximă a sumei obținute, iar pe a doua linie poziția (linia și coloana, separate printr-un spațiu) corespunzătoare elementului pentru care s-a obținut suma maximă.

Restricții și precizări

2 ≤ n ≤ 300
Elementele matricei sunt numere întregi dintre -10000 și 10000.

Exemplu

suma7.in

suma7.out

18
1 3

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

#include <fstream>

using namespace std;
ifstream fin("suma7.in");
ofstream fout("suma7.out");
int a[301][301],s[301][301] ,b[301],c[301],x[301],y[301],u[301],v[301],n;
int main()
{
    int sm,i,j,im,jm;
    fin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fin>>a[i][j];

            b[i]+=a[i][j];
            c[j]+=a[i][j];

            if(i>=j)
                x[i-j+1]+=a[i][j];
            else
                y[j-i+1]+=a[i][j];

            if(i+j<=n+1)
                u[i+j-1]+=a[i][j];
            else
                v[i+j-n]+=a[i][j];

        }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {

            s[i][j]=b[i]+c[j]-a[i][j];

            if(i>=j)
                s[i][j]+=x[i-j+1];
            else
                s[i][j]+=y[j-i+1];

            s[i][j]-=a[i][j];

            if(i+j<=n+1)
                s[i][j]+=u[i+j-1];
            else
                s[i][j]+=v[i+j-n];

            s[i][j]-=a[i][j];
        }
    sm=s[1][1];im=jm=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(s[i][j]>sm)
            {
                sm=s[i][j];im=i;jm=j;
            }
    fout<<sm<<endl;
    fout<<im<<<<jm<<endl;
    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 #1948 Suma7

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