Cod sursa(job #283711)
Utilizator | Data | 19 martie 2009 16:24:25 | |
---|---|---|---|
Problema | Deque | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include<fstream.h>
int n,k,v[5000001],a[5000001];
long long s;
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
int i,p,u;
f>>n>>k;
for (i=1;i<=n;i++) f>>v[i];
p=0;
u=1;
for (i=1;i<=n;i++)
{
while (p<=u&&v[i]<=v[a[u]]) u--;
a[++u]=i;
if (a[p]==i-k) p++;
if (i>=k) s+=v[a[p]];
}
/*for (i=0;i<n-k+1;i++)
{
min=5001;
for (j=i;j<i+k;j++)
if (min>v[j]) min=v[j];
s+=min;
}*/
g<<s;
g.close();
return 0;
}