Pagini recente » Cod sursa (job #2265438) | Cod sursa (job #2578990) | Cod sursa (job #370091) | Cod sursa (job #1094814) | Cod sursa (job #542996)
Cod sursa(job #542996)
#include<fstream>
#include<deque>
using namespace std;
#define maxn 5000001
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,a[maxn],d[maxn];
int front=1,back,i;//initializare back<=front din care rezulta ca deque-ul nu are niciun element (este vid)
long long S;
int main(){
f>>n>>k;
for(i=1;i<n;i++) f>>a[i];//citeste sirul dat
for(i=1;i<=n;i++) {
while(front<=back&&a[i]<=a[d[back]])back--; //cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
d[++back]=i; //adaugam pozitia elementului curent in deque
if(d[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[d[front]];
}
g<<S;
g.close();
return 0;
}