Pagini recente » Cod sursa (job #3177595) | Cod sursa (job #130484) | Cod sursa (job #3290) | Cod sursa (job #17316) | Cod sursa (job #363757)
Cod sursa(job #363757)
#include<fstream>
#include<iostream>
#include<list>
using namespace std;
list<int> nr,pos;
int k;
void baga(int x,int posi)
{
while( nr.size() && ( nr.back() >= x ) )
{
nr.pop_back();
pos.pop_back();
}
nr.push_back(x);
pos.push_back(posi);
if( posi - pos.front() >= k )
{
nr.pop_front();
pos.pop_front();
}
}
int minim()
{
return nr.front();
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,x;
scanf("%d %d",&n,&k);
for(int i=0; i<k; i++)
{
scanf("%d",&x);
baga(x,i);
}
long long rez = minim();
for(int i=k; i<n; i++)
{
scanf("%d",&x);
baga(x,i);
rez+=minim();
}
printf("%lld\n",rez);
return 0;
}