Cod sursa(job #1361857)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 26 februarie 2015 00:24:25
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<deque>

int main()
{
    FILE *fin,*fout;
    fin=fopen("secventa.in","r");
    fout=fopen("secventa.out","w");

    std::deque<int> deq;
    std::deque<int> pos;

    int n,k,t,m=-30000,s,e;
    fscanf(fin,"%d %d",&n,&k);

    for(int i=1;i<=k;i++)
    {
        fscanf(fin,"%d",&t);

        while(!deq.empty()&&t<deq.back())
        {
            deq.pop_back();
            pos.pop_back();
        }

        deq.push_back(t);
        pos.push_back(i);
    }

    m=deq.front();
    s=1;
    e=k;

    for(int i=k+1;i<=n;i++)
    {
        fscanf(fin,"%d",&t);

        if(pos.front()<=i-k)
        {
            pos.pop_front();
            deq.pop_front();
        }

        while(!deq.empty()&&t<deq.back())
        {
            deq.pop_back();
            pos.pop_back();
        }

        deq.push_back(t);
        pos.push_back(i);

        if(m<deq.front())
        {
            m=deq.front();
            s=i-k+1;
            e=i;
        }
    }
    if(m<deq.front())
    {
        m=deq.front();
        s=n-k+1;
        e=n;
    }
    fprintf(fout,"%d %d %d",s,e,m);
}