Cod sursa(job #1603611)

Utilizator danyvsDan Castan danyvs Data 17 februarie 2016 18:05:33
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <algorithm>
#include <deque>

using namespace std;

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,k,i;
    long long s,x;
    deque <pair <long long, int> > DQ;
    s=0;
    scanf("%d%d",&n,&k);
    for (i=1; i<=n; ++i)
        {
         scanf("%lld",&x);
         if (DQ.empty()) DQ.push_front(make_pair(x,i));
         else
            {
             while (DQ.back().first>x && !DQ.empty())
                DQ.pop_back();
             DQ.push_back(make_pair(x,i));
            }
         if (i>=k)
            {
             if (DQ.front().second<=i-k)
                 DQ.pop_front();
             s+=DQ.front().first;
            }
        }
    printf("%lld\n",s);
    return 0;
}