Cod sursa(job #1971034)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 19 aprilie 2017 19:36:20
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

int n, k, x, Queue[505], Deque[505];
int pr,ul=-1;
long long sum;

int main()
{
        freopen("deque.in", "r", stdin);
        freopen("deque.out", "w", stdout);

        scanf("%d %d", &n, &k);
        for(int i = 1; i <= k; ++i)
        {
                scanf("%d", &x);
                while(pr <= ul && Deque[ul] >= x) --ul;
                ++ul;
                Deque[ul] = x;
                Queue[ul] = i;
        }
        sum += Deque[pr];

        for(int i = k + 1; i <= n; ++i)
        {
                scanf("%d", &x);
                while(pr <= ul && Deque[ul] >= x) --ul;
                ++ul;
                Deque[ul] = x;
                Queue[ul] = i;
                if(i - Queue[pr] + 1 > k) pr++;
                sum += Deque[pr];
        }
        printf("%lld",sum);
        return 0;
}