Cod sursa(job #1251401)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 29 octombrie 2014 13:41:55
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
using namespace std;

int secv[50001], n, k, PozCr, Inceput, Sfarsit, Lungime, i;
long long SecvCr = -250000, Maxim = -250000;

int main()
{
    ifstream f("secv2.in");
    ofstream g("secv2.out");

    f>>n>>k;
    for (i=1; i<=n; i++)
        f>>secv[i];

    // Cauta intervalul subsecventei
    for (i=2; i<=n; i++)
    {
        if (SecvCr >= 0)
            SecvCr += secv[i];
        else
        {
            PozCr = i;
            SecvCr = secv[i];
        }
        if (SecvCr >= Maxim)
        {
            Inceput = PozCr;
            Sfarsit = i;
            Maxim = SecvCr;
        }
    }

    // Calculeaza lungimea subsecventei
    Lungime = Sfarsit - Inceput + 1;
    if (Lungime > k) // Daca lungimea subsecventei este mai mare decat k scrie pozitia de inceput, de sfarsit si suma
        g<<Inceput<<" "<<Sfarsit<<" "<<Maxim;
    else // Altfel scrie pozitiile de inceput, de sfarsit si suma 0
        g<<0<<" "<<0<<" "<<0;
    return 0;
}