Cod sursa(job #926402)
Utilizator | Data | 25 martie 2013 10:45:09 | |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <cstdio>
#include <deque>
using namespace std;
struct element
{
int val;
int poz;
};
deque<element> a;
int s;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k;
element crt;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
crt.poz=i;
scanf("%d",&crt.val);
while(i>1&&a.back().val>crt.val)
a.pop_back();
a.push_back(crt);
if(a.front().poz<=i-k)
a.pop_front();
if(i>=k)
s+=a.front().val;
}
printf("%d\n",s);
return 0;
}