Pagini recente » Cod sursa (job #1765970) | Cod sursa (job #2728048) | Cod sursa (job #3137223) | Cod sursa (job #1411330) | Cod sursa (job #630547)
Cod sursa(job #630547)
#include<fstream>
using namespace std;
struct comb{ int val,pos; }deq[500005];
int main(void){
ifstream fin("deque.in");
ofstream fout("deque.out");
int i,n,k,aux,c1=1,c2=1;
long long suma=0;
fin>>n>>k;
for(i=1;i<=n;++i){
fin>>aux;
if(deq[c1].pos<i-k)++c1;
if(i>k)suma+=deq[c1].val;
if(aux>deq[c2].val){
deq[++c2].val=aux;
deq[c2].pos=i;
}
else{
while(aux<deq[c2].val && c2>=c1)--c2;
++c2;
deq[c2].val=aux;
deq[c2].pos=i;
}
}
suma+=deq[c1].val;
fout<<suma; fin.close(); fout.close();
return 0;
}