Cod sursa(job #1052996)

Utilizator cioionutFMI Ionut Ciocoiu cioionut Data 12 decembrie 2013 00:22:40
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<iostream>
#include<fstream>
#include<deque>
#include<vector>
using namespace std;
int main()
{
    ifstream f("deque.in");
    ofstream g("deque.out");
    long long n,k,i,j,x;
    f>>n>>k;
    i=1;j=1;
    deque <long long> q;
    vector <long long> v;
    for(i=0;i<n;i++) {f>>x;v.push_back(x);}
    x=0;
    for(i=0;i<n;i++)
    {
        if(!q.empty()&&q.front()<=(i-k)) q.pop_front();
        if(!q.empty()) while(!q.empty()&&v[q.back()]>=v[i]) q.pop_back();
        q.push_back(i);
        if(i>=k-1) {
       if(q.front()==0&&j) {x+=v[q.front()];j=0;}
           else if(q.front()!=0) x+=v[q.front()];
        }
    }
          //if(!q.empty())  cout<<v[q.front()]<<" ";
        g<<x;
        f.close();
        g.close();
            return 0;
}