Cod sursa(job #2032029)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 4 octombrie 2017 12:19:44
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 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;

int main()
{
    fin>>n>>k;
    for(i=1; i<=n; ++i)
    {
        fin>>x;
        s[i]=s[i-1]+x;
    }
    Max=INT_MIN;
    Front=1; Back=0;
    for(i=1; i<=n-k; ++i)
    {
        while(Front<=Back && s[i]<=s[Deque[Back]]) --Back;
        Deque[++Back]=i;
        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;
}