Cod sursa(job #2032040)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 4 octombrie 2017 12:47:42
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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=k; 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-k]<=s[Deque[Back]]) --Back;
        Deque[++Back]=i-k;
        if(s[i]-s[Deque[Front]]>Max)
        {
            Max=s[i]-s[Deque[Front]];
            st=Deque[Front]+1; dr=i;
        }
    }
    fout<<st<<" "<<dr<<" "<<Max<<"\n";
    return 0;
}