Cod sursa(job #1846079)

Utilizator NicusorTelescu Nicolae Nicusor Data 12 ianuarie 2017 09:33:17
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <deque>

using namespace std;

struct pereche
{
    int valoare,indice;
};

deque <pereche> dq;

char s[200];

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,k;
    long long suma=0;
    scanf("%d %d\n",&n,&k);
    for (int i=1;i<=n;i++)
    {
        gets(s);
        int numar=0;
        bool bol=0;
        if (s[0]=='-')
            bol=1;

        for (int j=bol;s[j]!=0;j++)
            numar=numar*10+s[j]-'0';

        if (bol==1) numar=-numar;

        if (dq[0].indice==i-k)
            dq.pop_front();

        int sizee=dq.size();
        while (sizee>=1 && numar<dq[sizee-1].valoare)
            dq.pop_back(), sizee--;

        dq.push_back({numar,i});
        if (i>=k)
        suma+=dq[0].valoare;
    }
    printf("%d ",suma);
}