Cod sursa(job #1473723)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 20 august 2015 00:29:39
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <deque>
#define LIM 500023
#define DIM 10000
char buff[DIM];
int poz=0;
using namespace std;
int n,k;
deque<int>d,p;
void next()
{
    ++poz;
    if(poz>=DIM)
    {
        poz=0;
        fread(buff,1,DIM,stdin);
    }
}
int citeste()
{
    char semn='+';
    while((buff[poz]!='-')&&(!('0'<=buff[poz]&&buff[poz]<='9')))
    {
        next();
    }
    if(buff[poz]=='-')
    {
        semn='-';
        next();
    }
    int nr=0;
    while('0'<=buff[poz]&&buff[poz]<='9')
    {
        nr*=10;
        nr+=(buff[poz]-'0');
        next();
    }
    if(semn=='-') nr*=(-1);
    return nr;
}
int main()
{
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    fread(buff,1,DIM,stdin);
    n=citeste();
    k=citeste();
    int nr;
    for(int i=1;i<k;i++)
    {
        nr=citeste();
        while(!d.empty()&&d.back()>=nr)
        {
            d.pop_back();
            p.pop_back();
        }
        d.push_back(nr);
        p.push_back(i);
    }
    int maxim=-50000,pos=0;
    for(int i=k;i<=n;i++)
    {
        if(p.front()<=i-k)
        {
            p.pop_front();
            d.pop_front();
        }
        nr=citeste();
        while(!d.empty()&&d.back()>=nr)
        {
            d.pop_back();
            p.pop_back();
        }
        d.push_back(nr);
        p.push_back(i);
        if(maxim<d.front())
        {
            maxim=d.front();
            pos=i;
        }
    }
    printf("%d %d %d\n",pos-k+1,pos,maxim);
}