Dijkstra are complexitate O(M*logN), iar Bellman-Ford are O(M*N). Bellman Ford cu coada, asa cum l-ai facut tu, are aceeasi complexitate O(M*N), dar in practica e la fel de bun ca Dijkstra. Practic, niciodata nu o sa faca N*M pasi. Bellman-Ford e util cand ai costuri negative pe muchii, deoarece atunci Dijkstra nu merge.

Ordinea din fisierul de iesire are vreo importanta?

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;

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;
}

De ce nu merge codul acesta?

Cod:

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

long long cmmdc(long long a,long long b)
{
    long long c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

int main()
{
    ifstream fin("divmul.in");
    ofstream fout("divmul.out");
    long long t,i,x,y,k,a,b,c,nr;
    long long prod;
    fin>>t;
    for(k=1;k<=t;k++)
    {
        nr=0;
        fin>>x>>y;
        prod=x*y;
        for(i=1;i*i*x*x<=prod;i++)
        {
            a=i*x;
            if(prod%a==0)
            {
                b=prod/a;
                c=cmmdc(a,b);
                if(c==x&&a*b/c==y)
                {
                    nr+=2;
                    if(a*a==prod)
                        nr--;
                }
            }
        }
        cout<<nr<<"\n";
    }
    return 0;
}

De ce nu merge sa citesc tot sirul inainte si apoi sa-l parcurg?
Acesta este codul:

Cod:

#include <iostream>
#include <fstream>
#include <cstring>
#include <cctype>

using namespace std;
char a[1100010];
int main()
{
    ifstream fin("text.in");
    ofstream fout("text.out");
    int i;
    fin.getline(a,1100000);
    int n=strlen(a);
    int s=0,k=0,ok=1;
    for(i=0;i<n;i++)
    {
        if(isalpha(a[i]))
        {
            s++;
            if(ok)
                k++,ok=0;
        }
        else
            ok=1;
    }
        fout<<s/k;
    return 0;
}

Daca il fac identic, doar ca il citesc caracter cu caracter functioneaza.
Multumesc anticipat.

Ma chinui de mult la problema alfabetar, data la OMI Iasi 2011. Ea e foarte simpla, algoritmul merge, doar ca am avut probleme cu afisarea rezultatului. Daca deschideam fisierul out prin codeblocks, nu imi aparea nimic. Daca il deschideam dibn afara, prin notepad, imi aparea raspunsul corect. Doar ca evaluatorul imi spune peste tot Wrong Answer. Am reusit sa rezolv aceasta probleme cu o alta matrice, reusind sa afisez si cand deschideam dinauntru. Cu toate acestea, evaluatorul continua sa-mi spuna Wrong Answer pana si la exemplul problemei, la care sunt sigur ca e corect (am vazut cu ochii mei).
Va rog, daca ma puteti ajuta.
Multumesc anticipat.
Cod:

Cod:

#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;
char a[101][201];
char b[101][201];
int main()
{ifstream fin("alfabetar.in");
ofstream fout("alfabetar.out");
int n,i,j,maxim,k,l;
fin>>n;
for(i=0;i<=n;i++)
    fin>>a[i];
maxim=0;
for(i=1;i<=n;i++)
    {k=strlen(a[i]);
     if(k>maxim)
        maxim=k;
    }
for(j=maxim-1,l=0;j>-1;j--,l++)
    {for(i=0,k=0;i<n;i++,k++)
        {b[l][k]=a[i][j];
         if(a[i][j]==0)
            b[l][k]=' ';
        }
    }
for(i=0;i<=maxim;i++)
    {fout<<b[i];
     fout<<"\n";
    }
    return 0;
}