Cod sursa(job #1803708)

Utilizator alex.craciunCraciun Alexandru alex.craciun Data 11 noiembrie 2016 18:21:40
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define nmx 5000005


using namespace std;
FILE *f=fopen("deque.in","r");
FILE *f1=fopen("deque.out","w");
int v[nmx],n,k,s=0;
deque <int> q;
void citire( )
{
    fscanf(f,"%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);

}
void add(int i)
{
   while(!q.empty()&&v[q.back()]>v[i])
         q.pop_back();
    q.push_back(i);
}

void init()
{
    for(int i=1;i<=k;i++)
       add(i);
    s+=v[q.front()];
}
void eraser(int i)
{
    while(!q.empty()&&(i-q.front()+1>k))
          q.pop_front();
}
void rezolvare( )
{
    init( );
    for(int i=k+1;i<=n;i++)
    {
        add(i);
        eraser(i);
        s+=v[q.front()];
    }
}
int main()
{
    citire( );
    rezolvare();
    fprintf(f1,"%d",s);
    return 0;
}