948 Perle2

[•stef2n]

Aici puteti discuta despre problema Perle2.

[•blue_phoenix]

are cineva vreo idee ce e cu testul 9? ca iau tle pe ea, am incercat sa citesc intr-un buffer numerele si dupa aia sa parsez, dar merge chiar si mai incet. in general, am incercat cam tot ce mi-a trecut prin cap sa mearga mai rapid, dar tot tle iau....
asta e ceea ce fac:

Cod:

int x=n-1;
for(i=0;i<x;i++){
    if(diag[i]>0){
      //sunt pe linia i din "matrice"
      coloana[i]=diag[i];
      if(coloana[i]>max){max=coloana[i];}
      for(j=i+1;j<n;j++){
        coloana[j]=coloana[j-1]+diag[j];
        if(coloana[j]<=0)break;
        if(coloana[j]>max){
            max=coloana[j];
        }
      }
    }
}

datele le citesc cu stream-uri, in varianta care am vazut ca e cea mai rapida:
http://infoarena.ro/job_detail/631145

[•pauldb]

Iei Time Limit Exceeded pentru ca nu ai complexitatea buna. Problema se rezolva in O(N). Niste indicatii gasesti aici si aici.

Am scazut limita de timp si am reevaluat sursele. Nu era bine ca iti treceau 9 teste din 10 cu complexitate O(N^2).

[•blue_phoenix]

ok. mersi de linkuri, mi se paruse mie ca era prea usor sa fie asa:)

[•lucian666]

Dacă valoarea maximă posibilă este negativă, atunci Laura va prefera sa nu aleagă nici o perlă.
raspunsul va fi 0 in acest caz?

[•an_drey_curent]

Da