Cod sursa(job #1565039)

Utilizator redcrocodileIlies Andreea redcrocodile Data 10 ianuarie 2016 12:05:06
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque<int> val,ord;
long long s;
int n,k,i,x;
int main()
{
    f>>n>>k;
    for (i=1;i<=n;i++)
    {
        f>>x;
        while(!val.empty() and x<val.back())
        {
            val.pop_back();
            ord.pop_back();
        }
     val.push_back(x);
     ord.push_back(i);
     if(i>=k)
     {
         s+=val.front();
         while(!ord.empty() and i-ord.front()+1>=k)
         {
             val.pop_front();
             ord.pop_front();
         }
     }
    }
    g<<s;
    return 0;
}