Cod sursa(job #1054026)
| Utilizator | Data | 13 decembrie 2013 11:18:09 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <cstdio>
#include <deque>
using namespace std;
deque < int > q;
int i,j,n,m,k,x,a[5000005];
long long s;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d %d\n",&n,&k);
for(i=1; i<=n; i++)
{
scanf("%d\n",&a[i]);
while(!q.empty()&&a[q.back()]>a[i])
{
q.pop_back();
}
q.push_back(i);
while(q.front()<=i-k)
{
q.pop_front();
}
if(i>=k)
{
s+=a[q.front()];
}
}
printf("%lld\n",s);
return 0;
}
