Cod sursa(job #2161375)

Utilizator mrhammerCiocan Cosmin mrhammer Data 11 martie 2018 18:11:32
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
//ifstream fin("date.in");
//ofstream fout("date.out");
struct deq_m
{
    int val;
    int time_pos;
};
std::deque<deq_m> deq;
int n,k;
void print_deque()
{
    for(int i=0;i<deq.size();i++)
    {
        cout<<deq[i].val<<" ";
    }
    cout<<"\n";
}
void update_deque(int x,int y)
{
    int i;
    for(i=deq.size()-1;i >= 0;i--)
    {
        if(x < deq[i].val) deq.pop_back();
    }
    if(x == deq[0].val) deq.pop_front();
    deq_m d;
    d.val = x;
    d.time_pos = y;
    deq.push_back(d);
}
void check_front(int y)
{
    bool ok = false;
    while(ok == false)
    {
        if(y - deq[0].time_pos >= k-1)
        {
            deq.pop_front();
        }
        else
        {
            ok = true;
        }
    }
}
int main()
{
    fin>>n>>k;
    int k1;
    int s = 0;
    for(int i=0;i<n;i++)
    {
        fin>>k1;
        update_deque(k1,i);
        //print_deque();
        if(i >= k-1)
        {
            s+= deq[0].val;
        }
        check_front(i);
    }
    fout<<s;
}