Cod sursa(job #1783513)

Utilizator Walrus21andrei Walrus21 Data 19 octombrie 2016 03:52:48
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#define L 5000001

using namespace std;

struct s{int v;int p;};

int i,n,k,x,f,l;
long long sum;

s d[100];

int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    scanf("%d%d%d", &n, &k, &d[0].v);
    d[0].p=1;
    for(i=2; i<=n;i++)
    {
        scanf("%d", &x);
        if(d[f].p<=i-k) f++;
        if(x<=d[l].v)
        {
            while(x<=d[l].v&&l>=f) l--;
            d[++l].v=x;
            d[l].p=i;
        }
        else {d[++l].p=i; d[l].v=x;}
        if(i>=k) sum+=d[f].v;
    }
    printf("%lld",sum);
    return 0;
}