Cod sursa(job #783760)
| Utilizator |  zzz zzz misino |
Data | 3 septembrie 2012 20:30:47 |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.34 kb |
#include<fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,m,i,s,k,li,ls,d[500001],a[500001];
int main()
{f>>n>>k;
for(i=1;i<=n;++i)
f>>a[i];
li=0;
ls=1;
for(i=1;i<=n;++i)
{while(li>=ls&&a[i]<=a[d[li]])--li;
d[++li]=i;
if(d[ls]==i-k)
++ls;
if(i>=k)
s+=a[d[ls]];
}
g<<s<<'\n';
return 0;
}