Cod sursa(job #3211184)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 8 martie 2024 18:07:56
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include<deque>
#include<vector>
std::ifstream fin("deque.in");
std::ofstream fout("deque.out");
long long s=0;
std::deque<int>q;
std::vector<long long>vec;
void update(int pos)
{
    while(!q.empty() && vec[pos]<vec[q.back()])
        q.pop_back();
    q.push_back(pos);
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    int n, k;
    fin>>n>>k;
    long long val;
    for(int index=0; index<k; ++index)
    {
        fin>>val;
        vec.push_back(val);
        update(index);
    }
    s+=vec[q.front()];
   // fout<<vec[q.front()]<<' ';
    for(int index=k; index<n; ++index)
    {
        int pos=q.front();
        if(index-pos==k)
            q.pop_front();

        fin>>val;
        vec.push_back(val);
        update(index);
        s+=vec[q.front()];
       // fout<<vec[q.front()]<<' ';
    }
    fout<<s;
    return 0;
}