Cod sursa(job #2032033)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 4 octombrie 2017 12:33:11
Problema Secventa 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

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

int s[50001], Deque[50001];
int n, k, i, Max, Front, Back, x, st, dr, j;

int main()
{
    fin>>n>>k;
    for(i=1; i<=n; ++i)
    {
        fin>>x;
        s[i]=s[i-1]+x;
    }
    /*for(i=1; i<=n; ++i) fout<<s[i]<<" ";
    fout<<"\n";*/
    Max=INT_MIN;
    Front=1; Back=0;
    for(i=1; i<=n; ++i)
    {
        /*fout<<"FRONT: "<<Front<<" BACK: "<<Back<<"\n";
        for(j=Front; j<=Back; ++j) fout<<s[Deque[j]]<<" ";
        fout<<"\n\n";*/

        while(Front<=Back && s[i]<=s[Deque[Back]]) --Back;
        Deque[++Back]=i;
        if(Deque[Front]==i-k) ++Front;
        if(s[i+k]-s[Deque[Front]]>Max)
        {
            Max=s[i+k]-s[Deque[Front]];
            st=Deque[Front]+1; dr=i+k;
        }
    }
    fout<<st<<" "<<dr<<" "<<Max<<"\n";
    return 0;
}