Cod sursa(job #1410150)

Utilizator zpaePopescu Andreea zpae Data 30 martie 2015 21:33:19
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <deque>
using namespace std;
#define N 100001
#define MAX 5000005
ifstream in ("euclid3.in");
ofstream out ("euclid3.out");
deque <int> v,p;

int main()
{
    long long n,k,x,m=MAX,i,j,s=0;
    in>>n>>k;
    for(i=1;i<=k;i++)
    {
        in>>x;
        if(x<=m)
        {
            m=x;
            v.clear();
            p.clear();
        }
        v.push_back(x);
        p.push_back(i);
    }
    s+=v.front();
    for(i=k+1;i<=n;i++)
    {
        in>>x;
        v.push_back(x);
        p.push_back(i);
        if(x<v.front())
        {
            v.erase(v.begin(),v.end()-1);
            p.erase(p.begin(),p.end()-1);
        }
        else
        {
            if(p.front()<=i-k)
            {
                v.pop_front();
                p.pop_front();
                m=0;
                for(j=1;j<v.size();j++)
                    if(v[j]<v[m])
                        m=j;
                v.erase(v.begin(),v.begin()+m);
                p.erase(p.begin(),p.begin()+m);
            }
        }
        s+=v.front();
    }
    out<<s<<'\n';
}