Pagini recente » Cod sursa (job #757456) | Cod sursa (job #1205992) | Cod sursa (job #1378184) | Cod sursa (job #1492065) | Cod sursa (job #2823978)
#include <stdio.h>
#include <ctype.h>
// Program de Mircea Rebengiuc
// inceput pe 2021.11.12
#define MAXBUF (128 * 1024)
#define MAXQ 8388608
#ifdef LOCAL
#define DEBUG(var) printf("(!) [DEBUG] "#var" = %d\n", var)
#else
#define DEBUG(var)
#endif
// ------------------ CIRCULAR DEQUEUE ------------------
int deq[MAXQ];
int p, u;
static inline int empty(){
return p == u;
}
static inline int top_front(){
return deq[p];
}
static inline void pop_front(){
p = ((p + 1) & (MAXQ - 1));
}
static inline void pop_back(){
u = ((u - 1 + MAXQ) & (MAXQ - 1));
}
static inline int top_back(){
return deq[(u - 1 + MAXQ) & (MAXQ - 1)];
}
static inline void push_back( int val ){
deq[u] = val;
u = ((u + 1) & (MAXQ - 1));
}
// ------------------ CIRCULAR QUEUE ------------------
int q[MAXQ];
int qp, qu;
static inline void push( int val ){
q[qu] = val;
qu = ((qu + 1) & (MAXQ - 1));
}
static inline int pop(){
int ret = q[qp];
qp = ((qp + 1) & (MAXQ - 1));
return ret;
}
// inserts in data structure
static inline void insert( int val ){
push(val);
while( !empty() && top_back() > val )
pop_back();
push_back(val);
}
// deleltes from data structure
static inline void del(){
if( top_front() == pop() )
pop_front();
}
FILE *fin, *fout;
char ibuf[MAXBUF];
int ibp = MAXBUF - 1;
static inline int bgetc(){
if( (ibp = ((ibp + 1) & (MAXBUF - 1))) == 0 )
fread(ibuf, sizeof(char), MAXBUF, fin);
return ibuf[ibp];
}
static inline int fgetint(){
int n = 0, ch, semn = 1;
while( isspace(ch = bgetc()) );
if( ch == '-' ){
semn = -1;
ch = bgetc();
}
do
n = n * 10 + ch - '0';
while( isdigit(ch = bgetc()) );
return n * semn;
}
int main(){
fin = fopen("deque.in", "r");
fout = fopen("deque.out", "w");
int n, k, i;
long long sum;
p = u = qp = qu = 0;
n = fgetint();
k = fgetint();
for( i = 1 ; i < k ; i++ )
insert(fgetint());
sum = 0;
for( i = k - 1 ; i < n ; i++ ){
insert(fgetint());
DEBUG(top_front());
sum += top_front();
del();
}
fprintf(fout, "%lld\n", sum);
fclose(fin);
fclose(fout);
return 0;
}