Cod sursa(job #1599068)

Utilizator grimmerFlorescu Luca grimmer Data 13 februarie 2016 16:22:20
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;
deque<int> q;
vector<int> G;
int main()
{
    int i, k, n, x;
    int minn = 0;
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d%d", &n, &k);
    scanf("%d",&x);
    G.push_back(x);
    q.push_back(1);
    for(i=2; i<=n; ++i){
        scanf("%d", &x);
        G.push_back(x);

        while(!q.empty() && G[q.back()-1] > G[i-1])
            q.pop_back();
        q.push_back(i);
        if(i >= k && q.front() == i-k)
                q.pop_front();
        if(i >=k && q.front() >= i-k+1)
               minn += G[q.front()-1];
    }
    printf("%d",minn);
    return 0;
}