Cod sursa(job #2083112)

Utilizator MrRobotMrRobot MrRobot Data 7 decembrie 2017 03:30:11
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <limits.h>
#include <deque>
using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

deque <int> d;

int main()
{
    int n, k;
    fin>>n>>k;
    int i, x, indmincrt;
    long long suma;
    for(i=1; i<=k; i++)
    {
        fin>>x;
        if(d.empty() == 0)
        {
            while(d.back() > x && d.empty() == 0)
            {
                d.pop_back();
            }
            if(d.empty())
                indmincrt = i;
            d.push_back(x);
        }
        else
        {
            d.push_back(x);
            indmincrt = i;
        }
    }
    suma = d.front();
    //simuleaza 2 indici
    int j=k+1;
    i=1;
    while(j<=n)
    {
        fin>>x;
        if(d.empty() == 0)
        {
            while(d.back() > x && d.empty() == 0)
            {
                d.pop_back();
            }
            if(d.empty())
                indmincrt = j;
            d.push_back(x);
        }
        else
        {
            d.push_back(x);
            indmincrt = j;
        }

        //if(j - i >= k) //posibil sa fie mereu ok
        //{
            i++;
            //cout<<d.size()<<endl;
            if( (d.size() > 1) && !(i<=indmincrt && indmincrt<=j)  )
                d.pop_front();
            suma += d.front();
        //}
        j++;
    }
    fout<<suma;
}