Pagini recente » Cod sursa (job #1907895) | Cod sursa (job #1884682) | Cod sursa (job #2199826) | Cod sursa (job #2577928) | Cod sursa (job #541191)
Cod sursa(job #541191)
#include<fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,a[5000010],deque[5000010];
int front,back,i;
long long S;
int main(){
f>>n>>k;
for(i=1;i<n;i++) f>>a[i];//citeste sirul dat
front=1; back=0; //initializare back<=front din care rezulta ca deque-ul nu are niciun element (este vid)
for(i=1;i<=n;i++) {
while(front<=back && a[i]<=a[deque[back]]) back--; //cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
deque[++back]=i; //adaugam pozitia elementului curent in deque
if(deque[front]==i-k) front++; //daca elementul minim coincide cu cel de pe pozitia i-k, ii eliminam pozitia din deque, deoarece acesta nu mai conteaza pentru pasii >=i
if(i>=k) S+=a[deque[front]];
}
g<<S;
g.close();
return 0;
}