Problema cu triunghiu


(JustSM) #1

Incerc sa rezolv aceasta problema. Doar ca obtin doar 70 de puncte si nu inteleg cum as putea sa fac algoritmul mai eficient
Am incercat asta:

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("triunghi3.in");
ofstream g("triunghi3.out");
int i,j,n,s,d,poz,val,este;
long long A[1005][1005];
int main()
{
    f>>n;
    //declar toate elementele necesare cu -1 pentru a putea detecta numerele pozitive mai incolo
    //declar pentru n linii  si pentru fiecare linie i elemente(prima linie are doar 1 numar, a 2 doua nr etc, este triunghi)
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
        A[i][j]=-1;
    //citesc elementele din fisier, se cunoaste unul de pe fiecare coloana
    for(i=1;i<=n;i++){
        f>>poz;
        f>>val;
        A[n-i+1][poz]=val;
    }
    f.close();
    
	//se parcurge matricea linie cu linie, element cu element
    for(i=1;i<=n;i++) { //incep de la 2 deoarece pe fiecare linie se cunoaste un element iar linia 1 are doar 1 element
        este=0; /* pe fiecare linie e doar un element natural la inceput deci dupa ce se gaseste acel 
        		element se opreste cautarea pe linia curenta */
        for(j=1;j<=i && !este;j++) // j merge doar pana la i pt ca fiind triunghi fiecare prima linie are 1 elem, a doua 2 etc
        if(A[i][j]>=0) {
            //se completeaza elementele din stanga si din dreapta folosind elementele de pe linia anterioara si elementul gasit
            for(s=j-1;s>=1;s--)
                A[i][s]=A[i-1][s] - A[i][s+1];
            for(d=j+1;d<=i;d++)
                A[i][d]=A[i-1][d-1] - A[i][d-1];
            este=1;
        }
    }
	// se afiseaza numerele de pe ultima linie
    for(i=1;i<=n;i++)
        g<<A[n][i]<<" ";
    g.close();

    return 0;
}

Am pus si poza pentru a intelege mai bine
explicatie