Pagini recente » Cod sursa (job #2481865) | Cod sursa (job #2416193) | Cod sursa (job #440449) | Cod sursa (job #639598) | Cod sursa (job #2161334)
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.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[i].val) break;
}
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);
if(i >= k-1)
{
s+= deq[0].val;
}
check_front(i);
}
fout<<s;
}