Cod sursa(job #2215493)

Utilizator stefantagaTaga Stefan stefantaga Data 22 iunie 2018 13:21:14
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque <int> c;
long long n,v[50000001],s,i,k;
int main()
{

    f>>n>>k;
    for (i=1;i<=n;i++)
    {
        f>>v[i];
    }
    c.push_back(1);
    for (i=2;i<=n;i++)
    {
        while (!c.empty()&&v[c.back()]>v[i])
        {
            if (c.size()!=0)
            {
                c.pop_back();
            }
            else
            {
                break;
            }
        }
        c.push_back(i);
        if (c.back()-c.front()>=k)
        {
            c.pop_front();
        }
        if (i>=k)
        {
            s=s+v[c.front()];
        }
    }
    g<<s;
    return 0;
}