Cod sursa(job #538904)
Utilizator | razyelx razyelx | Data | 22 februarie 2011 01:54:17 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream.h>
#define N 5000001
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,k,s[N],deque[N],first,last;
long long sum=0;
int main(){
int i,j;
fin>>n>>k;
for (i=1; i<=n; i++)
fin>>s[i];
first = 1;
last = 0;
for (i=1; i<=n; i++){
while ( first <= last && s[deque[last]] >= s[i]) last--;
deque[++last] = i;
if (deque[first] == i-k)
first++;
if (i >= k ) sum+= s[deque[first]];
}
fout<<sum;;
return 0;
}