Cod sursa(job #2283937)
Utilizator | Andrei Tudor isa_tudor_andrei | Data | 16 noiembrie 2018 09:31:45 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <cstdio>
#define MAXN 5000000
using namespace std;
int v[MAXN],dq[MAXN];
int main() {
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int st,dr,s,n,i,k;
scanf("%d%d",&n,&k);
s = 0;
for( i = 0; i < n; i ++ )
scanf("%d",&v[i]);
st = 0;
dr = -1;
for( i = 0; i < n; i ++ ) {
if( st <= dr && dq[st] == i - k )
st ++;
while( st <= dr && v[i] <= v[dq[dr]] )
dr --;
dq[++dr] = i;
if( i >= k - 1 )
s += v[dq[st]];
}
printf("%d",s);
return 0;
}