Cod sursa(job #825114)

Utilizator cristalCiurdarean Andrei cristal Data 27 noiembrie 2012 15:05:47
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
#define INF 0x3f3f3f3f
ifstream is ("secv2.in");
ofstream os ("secv2.out");

long i,n,k;
long T[50005], S[50005], D[50005];
long maxim=-INF, front, back, st, dr;

int main()
{
    is >> n >> k;
    for ( i=1; i<=n; i++ )
    {
        is >> T[i];
        S[i]=S[i-1]+T[i];
    }
    back=0;
    front=1;
    for ( i=k; i<=n; i++ )
    {
    while ( S[i]> S[ D[back] ] && back>0 )
        back--;
    back++;
    D[back]=i;
    }
    for ( i=1; i<=n-k+1; i++ )
    {
        if ( D[front] < i+k-1 )
            front++;
        if ( maxim < S[D[front]]-S[i-1] )
        {
            maxim=S[D[front]]-S[i-1];
            st=i;
            dr=D[front];
        }
    }
    os << st << " " <<  dr << " " <<  maxim;
return 0;
}