318 Buline

[•aladin]

Cineva care a facut problema de 100 poate sa imi trimita un test mai mare apropiat de limite ca nu pot sa imi dau seama ce gresesc...sau un hint cum sa fac...iau doar 20,si iau testele pe care nu le iau cei cu 80

[•Anamaria20]

Si eu am probleme cu testele 8 si 9. Cum le-ati rezolvat? Nu-mi dau seama ce are. 

[•DaNutZ2UuU]

Sal.. stie careva de ce imi zice evaluatorul:

Cod:

Contactează autorul problemei: A apărut o eroare în rularea evaluatorului pe testul 1: Killed by signal 11(SIGSEGV).: timp 0ms: mem 248kb 

?

[•visanr]

Pune numele fisierelor corect. 

[•Sagunistu]

Am incercat sa rezolv problema fara deque, folosind subsecventa de elemente consecutive de suma maxima, dar iau doar 20 de puncte (pe testele carora celorlalti nu le merge).

Cod:

#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

int a[400010];

int main()
{
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    int n,i,x,y,s=0,p,l=0,smax=INT_MIN,pmax=0,lmax;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        if(y==0)
            a[i]=a[i+n]=-x;
        else
            a[i]=a[i+n]=x;
    }
    p=1;
    for(i=1;i<=2*n;i++)
    {
        s+=a[i];
        l++;
        if(s>smax)
        {
            if(l+p-1>n+p-1)
                break;
            smax=s;
            pmax=p;
            lmax=l;
        }
        if(s<=0)
        {
            if(i>n)
                break;
            p=i+1;
            l=0;
            s=0;
        }
    }
    fout<<smax<<" "<<pmax<<" "<<lmax;
    return 0;
}

[•RaduGabriel2012]

Iei doar 20 de puncte fiindca in rezolvarea ta poti sa iei un element de mai multe ori , lucru nepermis in problema . De exemplu cand ai toate numerele pozitive , sursa ta va lua fiecare element de 2 ori ceea ce e gresit. Deaia subsecventa ta trebuie sa aiba lungime cel mult n.

[•Sagunistu]

Programul meu nu cred ca ia un numar de mai multe ori. Am verificat pentru toate numerele pozitive.
Folosesc ca si conditie:

Cod:

if(l+p-1>n+p-1)
                break;

[•RaduGabriel2012]

Da , nu m-am uitat in sursa ta , am banuit doar. Oricum la tine in sursa mi se pare foarte ciudat faptul ca iesi cand subsecventa ta depaseste lungimea n . Pot exista si alte subsecvente, de lungime mai mica sau egala cu n si de suma mai mare ca smax care se termina in elementul la care tu iesi din for sau dupa el . De-aia ar trebui sa faci cu un deque. Nu prea cred ca ai cum sa faci fara.