Cod sursa(job #2044365)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 21 octombrie 2017 09:37:36
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

struct el{
    int val;
    int poz;
};

deque <el> DQ;
int n, k;
int s;

int main()
{
el y;
int x;
fin>>n>>k;
for (int i=1;i<=n;i++)
    {
     fin>>x;
     y.val=x;
     y.poz=i;
     while (!DQ.empty())
        {
         if (DQ.back().val>=y.val)
            DQ.pop_back();
            else break;
        }
     DQ.push_back(y);
     if (DQ.front().poz<=i-k)
         DQ.pop_front();
     if (i>=k)
     s+=DQ.front().val;
    }
fout<<s<<'\n';
fin.close();
fout.close();
return 0;
}