Cod sursa(job #1675112)

Utilizator MDiana15Diana M MDiana15 Data 5 aprilie 2016 09:09:45
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <deque>
using namespace std;
deque<int>de;
long long s=0,i,j,n,k,v[5000001];
int main()
{
    ifstream f("deque.in");
    ofstream g("deque.out");
    f>>n>>k;
    for(i=1;i<=n;i++)
         f>>v[i];
    de.push_back(1);
    for(i=2;i<=n;i++)
        {
         while(!de.empty()&&v[de.back()]>v[i])
         {
            if(de.size()==0)break;
            else de.pop_back();
         }
         de.push_back(i);
         if(de.back()-de.front()>=k){de.pop_front();}
         if(i>=k)s=s+v[de.front()];
        }
    g<<s;
    return 0;
}