Cod sursa(job #1197663)

Utilizator taigi100Cazacu Robert taigi100 Data 13 iunie 2014 09:44:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
/*
    Keep It Simple!
*/

#include<fstream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MaxN 500005

int A[MaxN],Deque[MaxN],N,K,best,beg;
char buffer[8*MaxN];

int main()
{
  //  ifstream f("secventa.in");
    FILE *f = fopen("secventa.in","r");
    ofstream g("secventa.out");
    best = -(1<<30);
    fscanf(f,"%d%d\n",&N,&K);
    fgets(buffer,8*MaxN,f);
    int size = strlen(buffer);
    int sign=1,number=0;
    int cnt = 0;
    for(int i=0;i<size;i++)
    {
        if(buffer[i] == '-')
            sign = -1;
        else if (buffer[i] != ' ')
        {
            number = number*10 + buffer[i] -'0';
        }

        if(buffer[i] == ' ' || buffer[i] == '\n')
        {
                A[++cnt] = number*sign;
                number = 0;
                sign = 1;
        }
    }

    int Front = 1;
    int Back = 1;
    Deque[1] = 1;
    for(int i = 2; i < K; ++i)
    {
             while(Front <= Back && A[i] <= A[ Deque[Back] ]) Back--;
             Deque[++Back] = i;
    }
    for(int i=K;i<=N;i++)
    {
        while(Front <= Back && A[i] <= A[Deque[Back]]) Back--;
        Deque[++Back] = i;

        if(Deque[Front] == i-K) Front++;

        if(i>=K)
        {
            if(A[Deque[Front]] > best)
            {
                best = A[Deque[Front]];
                beg = i;
            }
        }
    }
    g << beg-K+1 << " " << beg << " " << best;

    g.close();
    return 0;
}