Cod sursa(job #1124322)
Utilizator | Bucevschi Alexandru alex_bucevschi | Data | 26 februarie 2014 12:05:50 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <cstdio>
#include <deque>
using namespace std;
deque<int> Q;
int n,i,k,v[5000010];
long long sol;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<k;i++)
{
scanf("%d",&v[i]);
while(Q.size()&&v[Q.back()]>=v[i])Q.pop_back();
Q.push_back(i);
}
for(;i<=n;i++)
{
scanf("%d",&v[i]);
while(Q.size()&&v[Q.back()]>=v[i])Q.pop_back();
Q.push_back(i);
if(i-Q.front()==k)Q.pop_front();
sol+=v[Q.front()];
}
printf("%lld",sol);
}