Cod sursa(job #305039)

Utilizator utcistuBarcau Tomsa utcistu Data 15 aprilie 2009 23:52:56
Problema Deque Scor 25
Compilator c Status done
Runda Arhiva educationala Marime 1.7 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct elem
{
    int index;
    int value;
    struct elem *next,*prev;
}DequeT;

DequeT *createDequeElem(int x,int index)
{
    DequeT *buf;
    buf=(DequeT *)malloc(sizeof(DequeT));
    buf->value=x;
    buf->index=index;
    buf->next=NULL;
    buf->prev=NULL;
    return buf;
}

void insertDequeElem(DequeT *first,DequeT *last,DequeT* elem)
{
    DequeT *aux,*tmp;
    for (aux=last->prev;aux!=first;)
    {
        if (aux->value>=elem->value)
        {
            tmp=aux;
            aux=aux->prev;
            aux->next=last;
            last->prev=aux;
            free(tmp);
        }
        else
        {
            break;
        }
    }
    elem->prev=last->prev;
    last->prev->next=elem;
    last->prev=elem;
    elem->next=last;
}

void deleteDeque(DequeT *first)
{
    DequeT *tmp;
    tmp=first->next;
    tmp->next->prev=tmp->prev;
    tmp->prev->next=tmp->next;
    free(tmp);
}

int main()
{
    DequeT first,last,*buf;
    first.next=&last;
    first.prev=NULL;
    last.prev=&first;
    last.next=NULL;
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,x,k,i,sum=0;
    scanf("%d %d",&n,&k);
    for (i=1;i<=k;i++)
    {
        scanf("%d",&x);
        buf=createDequeElem(x,i);
        insertDequeElem(&first,&last,buf);
    }
    sum+=first.next->value;
    for (i=k+1;i<=n;i++)
    {
        scanf("%d",&x);
        buf=createDequeElem(x,i);
        if (i-first.next->index==k) deleteDeque(&first);
        insertDequeElem(&first,&last,buf);
        sum+=first.next->value;
    }
    printf("%d",sum);
    fclose(stdout);
}