Pagini recente » Cod sursa (job #746248) | Cod sursa (job #2902035) | Cod sursa (job #23086) | Cod sursa (job #2145978) | Cod sursa (job #305039)
Cod sursa(job #305039)
#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);
}