Pagini recente » Cod sursa (job #3252763) | Cod sursa (job #1786303) | Cod sursa (job #208498) | Cod sursa (job #2621526) | Cod sursa (job #1097432)
#include <fstream>
#include <deque>
#include<utility>
#define mp(x,y) make_pair(x,y)
using namespace std;
FILE* f=freopen("deque.in","r",stdin);
FILE* o=freopen("deque.out","w",stdout);
typedef pair<long long,int> pr;
deque<pr> dq;
int n,k;
void Insert(long long x, int p)
{
while(!dq.empty()&&dq.back().first>=x)
dq.pop_back();
dq.push_back(mp(x,p));
}
int main()
{
scanf("%d%d",&n,&k);
long long x;
for(int i=0;i<k;++i) {
scanf("%lld",&x);
Insert(x,i);
}
long long sum=0;
for(int i=k;i<n;++i)
{
sum+=dq.front().first;
while(!dq.empty()&&dq.front().second<=i-k)
dq.pop_front();
scanf("%lld",&x);
Insert(x,i);
}
printf("%lld",sum+dq.front().first);
return 0;
}