Cod sursa(job #1059104)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 16 decembrie 2013 10:06:58
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <deque>

using namespace std;
deque <int> q;
deque <int> :: iterator it;
int v[5000010],i,k,n,s;
bool ok;
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++)
    scanf("%d",&v[i]);
    i=1;
    ok=true;
    q.push_back(1);
    for(i=2;i<=k;i++){
        while(!q.empty()&&v[q.end()]>v[i]) q.pop_back();
        q.push_back(i);
    }
    s=0;
    i=k+1;
    for(i=k+1;i<=n;i++)
    {
        s+=v[q.front()];
        while(!q.empty()&&v[q.end()]>v[i]) q.pop_back();
        q.push_back(i);

        if (i-k==v[q.front()]) q.pop();

    }
    printf("\n%d",s);
    return 0;
}