Cod sursa(job #593873)
Utilizator | Andrei C. Smaug- | Data | 5 iunie 2011 00:11:54 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <cstdio>
#define MAXN 5000000
int main(){
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int N, K, D[MAXN], P[MAXN], l, r, i, a;
long long res = 0;
scanf("%d%d", &N, &K);
for(i=0; i<N; i++){
scanf("%d", &a);
if(l<=r && i-P[i]>=K-1)
l++;
while(l<=r && a<=D[r])
r--;
r++;
D[r]=a;
P[r]=i;
if(i>=K)
res+=D[l];
}
printf("%d\n", res);
return 0;
}