Cod sursa(job #1684447)

Utilizator EberardoVladianu Cosmin Eberardo Data 11 aprilie 2016 01:41:54
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream fin("secventa2.in");
ofstream fout("secventa2.out");

struct element
{
    int poz,val;
    element(int poz=0, int val=0):
        poz(poz),val(val){}
};

int suma,suma_inceput,pozi,pozf,suma_max,indice=-1;
int n,k;
deque<element> q;

void citire()
{
    int i,x,j;
    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
        fin>>x;
        q.push_back(element(i,x));
        suma_max+=x;
    }
    suma=suma_max;
    pozi=1;
    pozf=k;
    for(i;i<=n;i++)
    {
        indice++;
        fin>>x;
        suma_inceput+=q[indice].val;
        if(suma_inceput<0)
        {
            for(j=0;j<=indice;j++)
                q.pop_front();
            suma-=suma_inceput;
            suma_inceput=0;
            indice=-1;
        }
        q.push_back(element(i,x));
        suma+=x;
        if(suma>suma_max)
        {
            suma_max=suma;
            pozi=q.front().poz;
            pozf=q.back().poz;
        }
    }

}

int main()
{
    citire();
    fout<<pozi<<' '<<pozf<<' '<<suma_max;
    return 0;
}