Cod sursa(job #2039777)

Utilizator GranuVladGranu Dragos-Vlad GranuVlad Data 14 octombrie 2017 21:50:04
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream F("secv2.in");
ofstream G("secv2.out");
long long n,k,i,x,S[50005],Deque[50005],Front,Back,Max,dr,st;
int main ()
{
    F>>n>>k;
    for(i=1;i<=n;i++)
    {
        F>>x;
        S[i]=S[i-1]+x;
    }
    Front=1;
    Back=0;
    Max=-250005;
    for(i=k;i<=n;i++)
    {
        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]];
            dr=i;
            st=Deque[Front]+1;
        }
    }
    G<<st<<" "<<dr<<" "<<" "<<Max;
    return 0;
}